안녕하세요 큰돌님. 풀이를 몇번을 봤는데도 이해가 가지 않아서 질문드립니다. 이분탐색으로 찾으려는 것 - 실제 필요한 시간보다 조금 더 큰 시간 - 즉, ret이 놀이기구를 타는데 걸린 총 시간이 됨 ret - 1 / a[i] - ex) 문제 예시 들어주신 것처럼 4분이 딱 되었을 때 새롭게 타는 사람 수를 빼주기 위해 하는 로직 전체 묶음을 다 처리하고 놀이기구에 아무도 안 탄 상태로 가정하고 그 부분부터 한명씩 태우는 로직 이렇게 파악하긴 했는데, 아무리 봐도 2번, 3번이 전혀 이해가 가지 않습니다... 놀이기구 수만큼을 바로 태울 필요가 있나요? 처음 시작을 temp = m으로 시작하지 않고 temp = 0을로 시작하면 4분일 때 딱 7명 태운걸로 나와서 ret - 1 / a[i] 로직을 안해도 되지 않나요? 그리고 마지막에 총 걸린시간(ret) % a[i] 로직이 어떤 의미인건지 이해가 안 됩니다 ㅠㅠ 아래는 제가 선생님 코드를 이해하려고 주석을 달아본 코드입니다. #include<bits/stdc++.h> using namespace std; #define max_n 60000000004 #define MAX_M 10004 typedef long long ll; // ret : 총시간, temp가 m : 여기서 부터 시작 ll n, m, a[MAX_M], lo, hi = max_n, ret, mid, temp; bool check(ll mid) { temp = m; // 놀이기구 수만큼은 바로 태울 수 있으므로 m명은 태우고 시작 for (int i = 0; i < m; i++) temp += mid / a[i]; return temp >= n; // 총 걸리는 시간이 mid일 때 n명이상 태울 수 있는지 } int main() { cin >> n >> m; for (int i = 0; i < m; i++) cin >> a[i]; if (n <= m) { cout << n; return 0; } while (lo <= hi) { mid = (lo + hi) / 2; if (check(mid)) { ret = mid; // 총 걸린 시간 hi = mid - 1; } else lo = mid + 1; } // temp : 4분까지 태운 학생 수 -> 4분이 딱 됐을 때 바로 추가로 태울 수 있는데 그걸 뺀 순수하게 4분까지 태운 학생 수 temp = m; for (int i = 0; i < m; i++) temp += ((ret - 1) / a[i]); // 4분부터 시작해서 다시 순차적으로 놀이기구 태움 -> 즉, 여기서는 놀이기구에 아무도 타있지 않은 초기 상태임 for (int i = 0; i < m; i++) { if (ret % a[i] == 0) temp++; // % 연산의 결과가 0이 아날 경우 == 놀이기구에 이미 학생이 탑승되어 있음 if (temp == n) { cout << i + 1 << "\n"; return 0; } } return 0; }
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 시간 초과라고 뜨는데, 더 빠른 방법이 있나요?? import java.io.*; import java.util.*; class Node{ int v; int c; Node(int v, int c){ this.v=v; this.c=c; } } public class Main { public static ArrayList<Node>[] graph; public static int n,m,s, e; public static void main(String[] argvs) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); graph = new ArrayList[n+1]; for(int i=1;i<=n; i++) graph[i] = new ArrayList<>(); for(int i=0; i<m; i++) { int a=sc.nextInt(); int b=sc.nextInt(); int c=sc.nextInt(); graph[a].add(new Node(b,c)); graph[b].add(new Node(a,c)); } s=sc.nextInt(); e=sc.nextInt(); int lt=1; int rt = 1000000000; int answer=0; while(lt<=rt) { int mid = (lt+rt)/2; if(count(mid)==1) { //e정점까지 갈 수있으면 answer=mid; lt = mid+1; //최대의 답을 찾아야하니까 } else rt = mid-1; } System.out.print(answer); } public static int count(int limit) { int[] ck = new int[n+1]; Queue<Node> q = new LinkedList<>(); q.add(new Node(s,0)); ck[s]=1; while(!q.isEmpty()) { Node now = q.poll(); int nowx = now.v; int nowc = now.c; for(Node ob : graph[nowx]) { if(ob.c>=limit && ck[ob.v]==0) { q.add(new Node(ob.v, ob.c)); ck[ob.v]=1; } } } return ck[e]; //마지막 점까지 갈수 있다면 1리턴, 아니면 0리턴 } }
입력 순서가 BACDE 이면 HashMap을 배열로 생각하였을 때, 순서대로 저장된다면 KeySet()의 배열은 [B, A, C, D, E]가 되는게 맞지 않나요? for(char x : keySet())의 출력 값이 ABCDE로 나오는 것을 보면 별다른 sort과정 없이 HashMap에서 Key 값을 정렬해서 출력해주는 것으로 보입니다. HashMap에 존재하는 Key값들이 자동적으로 정렬이 되고 있다고 봐도 될까요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 ^^ 강의 너무 잘 듣고 있습니다. DP 문제를 풀다보면.., 시작하기 전에 해당 문제를 바텀업으로 풀어야할지, 탑바텀으로 풀어야할지 어떻게 결정할 수 있을까요? 제 느낌은 바텀업풀이가 점화식을 유도할 수 있다면 코드 자체가 간단하여(재귀호출x) 구현 난이도가 쉬운데, 점화식을 생각하는 과정이 경우에 따라 매우 어려운것 같습니다. 탑바텀 풀이는 완전탐색과 동일한 상태에서 메모이제이션 을 잘 정의함으로써 문제를 풀 수 있는데, DP배열의 상태정의를 어떻게 하느냐에 따라, 테스트케이스는 맞지만 제출시 틀리는 결과가 나오는 경우가 종종있습니다 (구현에서 실수 잦음) 어떤 식으로 DP의 풀이를 결정하고 문제를 들어가는지 질문드려요. 감사합니다.!!
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 아래와 같이 작성했는데, 4번째 테스트 케이스에서 답이 출력 되지 않습니다. 어디가 잘 못된건지 궁금합니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] argvs) { Scanner sc = new Scanner(System.in); int s=sc.nextInt(); int e=sc.nextInt(); int k=sc.nextInt(); int[] ck = new int[10001]; for(int i=0; i<k; i++) { //웅덩이 체크 int a=sc.nextInt(); ck[a]=1; } Queue<Integer> q = new LinkedList<>(); q.add(s); int L=0; while(!q.isEmpty()) { int len = q.size(); for(int i=0; i<len; i++) { int now = q.poll(); if(now==e) { System.out.print(L); System.exit(0); } for(int nx : new int[] {now-1,now+1,now+5}) { if(nx>=1 && nx<10001 && ck[nx]==0) { //이동할 수 있는 범위이고, 아직 방문 안했고, 웅덩이가 아니라면 ck[nx]=1; q.add(nx); } } } L++; } } }
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 사과나무 문제에 대해서 좌표를 잡은 다음에 즉 중앙갑을 (2,2)라는 값을 두고 abs 즉 절대값 함수를 이용하여 거리가 n/2를 이용하여 2 이하인 값의 범위 까지만 더해서 해도 괜찮은 가요? 즉 거x,y축 까지의 거리가 2 이하인 블록의 합을 구하는 방식입니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. dp를 작성하는 else 부분에서 배열의 범위가 벗어났다고 뜨는데, 어디가 잘 못 된건가요??? import java.io.*; import java.util.*; public class Main { public static void main(String[] argvs) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int[][] map = new int[n][m]; int[][] dp = new int[n][m]; for(int i=0; i<n; i++) { String s=sc.next(); for(int j=1; j<=m;j++) { map[i][j]=s.charAt(j)-'0'; } } for(int i=0; i<n ; i++) { for(int j=0; j<m; j++) { if(map[i][j]==0) dp[i][j]=0; else { //에러 부분(배열 범위 벗어남) int a=map[i-1][j]; int b=map[i][j-1]; int c=map[i-1][j-1]; int k = Math.min(a, Math.min(b, c)); dp[i][j] = k; } } } } }
안녕하세요 선생님. 구현 알고리즘에 대해 취약한 것 같아 질문 드립니다. 현재 1-O까지 풀면서 답안을 안 보고 푼건은 2번 정도인 것 같습니다. 구현 유형의 알고리즘이 약하다고 생각됩니다. 이런 와중에 2주차 그래프이론을 바로 학습하는게 맞을지, 아니면 구현 관련 알고리즘을 좀 더 찾아서 풀어보는게 맞을지 잘 모르겠습니다.
안녕하세요 선생님, 올려주신 강의 잘 듣고 있습니다. BFS를 이용하여 3-D 문제를 풀고 있습니다. http://boj.kr/c6c17d2eb9a749febe75792df0897caf Tree 깊이가 변할 때마다 fire() 라는 함수를 사용하여 불의 위치를 업데이트하는 방법으로 구현했습니다. 예제는 잘 통과하는데, 성공하지 못했습니다. 혹시 반례를 알 수 있을까요? 감사합니다.
재귀를 이용해서 dp를 하는 방식이 아닌 선생님께서 배낭채우기 할 때 처럼 표를 완성하여 dp를 했는데 무엇이 문제 인지 잘 모르겠습니다. 이 문제에서는 표에 넣을 수 있는 보석의 인덱스를 저장을 했고 표가 완성되면 넣어준 보석을 보석목록에서 제거하고 다음 가방을 완성하는 방식으로 코드를 작성했는데 무엇이 문제인지 잘 모르겠습니다. http://boj.kr/2b01ce15326a43c9ad3c8f340157eab3
현재 큰돌 강사님이 풀어주신 문제 해설은 이해 됐습니다. 그런데 scv갯수가 주어지고 한 개체를 한번에 여러번 공격을 못하기에 (모든 scv의 총 체력/한번에 줄 수 있는 데미지)이렇게 해서 구할 수도 있지 않을까 했습니다. 이를 바탕으로 코드를 썻으나 틀렸다고 나오는데 이게 왜 되지 않는지 몰라서 질문드립니다. 다음은 해당 코드입니다. http://boj.kr/dab5e07b909146eba418c449e7c219f9
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 테스트케이스 4번, 5번에서 에러가 뜹니다. 어디가 잘 못 된건지 궁금합니다. import java.io.*; import java.util.*; class Node implements Comparable<Node>{ int v1; int v2; double c; Node(int v1, int v2, double c) { this.v1=v1; this.v2=v2; this.c=c; } @Override public int compareTo(Node o) { //double형은 이렇게 한다. if(this.c<o.c) return -1; else return 1; } } public class Main { public static int n,m; public static int[] unf; public static ArrayList<Node> graph = new ArrayList<>(); public static ArrayList<Integer> x = new ArrayList<>(); public static ArrayList<Integer> y = new ArrayList<>(); public static int find(int v) { if(v==unf[v]) return v; else return unf[v] = find(unf[v]); } public static void union(int a, int b) { int fa = find(a); int fb = find(b); if(fa!=fb) unf[fa] = fb; } public static void main(String[] argvs) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); unf = new int[n]; for(int i=0; i<n; i++) unf[i] = i; for(int i=0; i<n; i++) { int a=sc.nextInt()-1; int b=sc.nextInt()-1; x.add(a); y.add(b); } for(int i=0; i<n; i++) { //점과 점 사이의 거리를 구하는 구문 for(int j=i+1; j<n; j++) { double dis = Math.sqrt((x.get(j)-x.get(i)) *(x.get(j)-x.get(i)) + (y.get(j)-y.get(i)) * (y.get(j)-y.get(i))); graph.add(new Node(i,j,dis)); } } for(int i=0; i<m; i++) { //이미 연결되어 있는 점들은 union해준다 int a=sc.nextInt(); int b=sc.nextInt(); union(a-1,b-1); } Collections.sort(graph); double answer=0; for(int i=0; i<graph.size(); i++) { //크루스칼 int fa = find(graph.get(i).v1); int fb = find(graph.get(i).v2); double cost = graph.get(i).c; if(fa!=fb) { //union(fa, fb); unf[fa] = fb; answer+=cost; } } System.out.format("%.2f", answer); //소수점 출력은 System.out.format으로 } }
안녕하세요 선생님. 예제도 다 맞는데 4%에서 틀렸습니다.가 나옵니다 ㅠㅠ 제 코드에 어느 부분이 문제인지 모르겠어서 질문드립니다.. 아래는 제가 제출한 코드입니다. #include<bits/stdc++.h> using namespace std; typedef long long ll; ll x, y, z, lo, hi, ret = -1; bool check(ll mid) { ll change_z = (double)(y + mid) / (x + mid) * 100; return change_z > z; } int main() { cin >> x >> y; // x : 게임 횟수, y : 이긴 횟수, z : 승률(y / x * 100) z = (double)y / x * 100; lo = 1; hi = 1e9; while(lo <= hi) { ll mid = (lo + hi) / 2; if(check(mid)) { hi = mid - 1; ret = mid; } else lo = mid + 1; } cout << ret << "\n"; }
