본문 바로가기

Problem Solving

 (135)
[ BOJ 백준 2610번 - 회의준비 ] 해설 및 코드 https://www.acmicpc.net/problem/2610 목적 필요한 위원회의 개수와, 각 위원회에서 누가 대표로 선정돼야 하는지 구하자. 접근법 1. 알고있는 사람끼리 같은 위원회에 속해야 한다. 따라서 k는 알고있는 사람 네트워크의 개수라고 할 수 있다. 2. 각 위원회의 대표는 네트워크의 중간에 있어야 한다. (가장 먼 사람과의 거리가 최소가 되어야 하므로...) 3. 플로이드 와샬 알고리즘을 적용하여 각 노드간 최단 거리를 구하고, 각 위원회의 대표를 정해서 오름차순으로 정렬한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 ..
[ BOJ 백준 1507번 - 궁금한 민호 ] 해설 및 코드 https://www.acmicpc.net/problem/1507 목적 모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값과 그 때, 모든 도로의 시간의 합을 구하자. 접근법 1. 플로이드 와샬 알고리즘으로 a에서 b로의 최단 거리를 구한 결과(인접행렬)가 주어졌을 때, 이를 알고리즘 수행 이전으로 돌려보라는 문제이다. 단 도로의 개수를 최소로 하기 위해 불필요한 도로는 모두 제거해야 한다. 2. 인접행렬에서 지울 수 있는 도로에 해당하는 요소를 INF값으로 할당한다. 도로 s[i][j]는 s[i][k] + s[k][j] == s[i][j]를 만족하는 k가 존재한다면 지워나간다. 3. 초기 상태의 인접 행렬에서 시간의 합을 구하고, 재차 플로이드 와샬 ..
[ BOJ 백준 10360번 - The Mountain of Gold? ] 해설 및 코드 https://www.acmicpc.net/problem/10360 목적 Ledang Pool들을 거쳐 Ledang Mountain에 과거에 도달할 수 있는지 구하자. 접근법 1. 음의 사이클에서 0지점(Ledang Mountain)으로 가는 길이 있는지 확인하면 된다. 2. 음의 사이클 판별을 위해 벨만 포드 알고리즘을 적용하고, 그때마다 현재 지점에서 0지점으로 갈 수 있는 지 여부를 배열에 저장한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #define f(i,l,r) for(int i=l;i> n >> m; f(i, 1..
[ Codeforces 1296B - Food Buying ] 해설 및 코드 https://codeforces.com/contest/1296/problem/B Problem - B - Codeforces codeforces.com 목적 초기에 s만큼의 금액이 주어지고, 사용한 금액의 10%(소수점 이하 무시)를 돌려받을 때, 최대로 사용할 수 있는 금액을 구하자. 접근법 1. cashback을 최대로 만들 수 있게 금액을 사용하면 된다. 2. 10으로 나눈 나머지는 돌려받지 못하고 몫만 돌려받으므로, 10의 배수의 금액만 사용하여 불필요한 지출을 줄이자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #define f(i,l,r) for(int i=l;i> t; while (t--) { int s; cin >> s; int ..
[ BOJ 백준 1219번 - 오민식의 고민 ] 해설 및 코드 https://www.acmicpc.net/problem/1219 목적 출발 도시에서 도착 도시까지 가는데, 중간에 여러 도시를 거쳐 얻을 수 있는 최대 이윤을 구하자. 접근법 1. 사이클이 발생 여부를 확인하기 위해 벨만 포드 알고리즘을 적용한다. 2. 사이클이 발생할 경우 사이클에서 도착 도시까지 가는 경로가 존재하는지 확인하기 위해 플로이드 와샬 알고리즘을 적용한다. 3. 발생할 수 있는 최대 이윤은 int 범위를 넘어갈 수 있으므로 타입에 주의한다. (100개의 도시가 100개의 교통수단으로 가장 큰 사이클을 형성할 때, 벨만 포드 알고리즘 적용 시, 비용이 100*100*1000000 = 10^10 까지 커질 수 있기 때문이다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..
[ BOJ 백준 1956번 - 운동 ] 해설 및 코드 https://www.acmicpc.net/problem/1956 목적 도로의 길이의 합이 가장 작은 사이클을 찾자. 접근법 1. a마을에서 출발하여 a마을로 도착하는 길이의 최소값을 구해야 한다. 2. 다대다 경로 검색 알고리즘인 플로이드 와샬을 적용하여, s[i][i] (i는1이상 v이하)의 최소값을 찾는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #define f(i,l,r) for(int i=l;i> v >> e; f(i, 1, v)f(j, 1, v) s[i][j] = INF; while (e--) { int a, b, c; cin >> a >> b >> c; s[a][b] = c;..
[ BOJ 백준 11562번 - 백양로 브레이크 ] 해설 및 코드 https://www.acmicpc.net/problem/11562 목적 a에서 b로 가는데, 최소 몇 개의 일방통행인 길을 양방향 통행으로 바꿔야 하는지 구하자. 접근법 1. 다대다 경로 검색 문제로서, 플로이드 와샬 알고리즘을 적용한다. 2. 입력값에 따라 알고리즘에 사용될 배열 값을 0, 1, INF로 설정해준 뒤, 슥삭... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #define f(i,l,r) for(int i=l;i> n >> m; f(i, 1, n)f(j, 1, n) { if (i == j)s[i][j] = 0; else s[i][j] = N; }..
[ BOJ 백준 2616번 - 소형기관차 ] 해설 및 코드 https://www.acmicpc.net/problem/2616 목적 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하자. 접근법 1. s[i][j]는 i번째 객차부터 j번째 소형 기관차로 손님을 운송할 때의 최대값으로 정한다. 2. 그러면 i번째 객차를 끄는 경우와 i + 1번째 객차부터 끄는 경우의 최대값을 취하게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include #define f(i,l,r) for(int i=l;i n || j == 3)return 0; int& ref = s[i][j]; if (ref != -1)return ref; return ref = ma..

티스토리툴바