문제 https://www.acmicpc.net/problem/25760 25760번: 귀경길 교통상황을 알려드립니다 정현이가 살고 있는 나라에는 각 지역을 연결하는 도로망이 있다. 도로망은 총 $N$개의 지점과 두 지점을 연결하는 $N-1$개의 양방향 도로로 구성되어 있으며, 모든 두 지점 사이를 도로망으로 이 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 생각해본 풀이의 예외 케이스를 도저히 찾지 못해서 다른 분의 풀이를 참고해서 해결하였다. 틀린 풀이 일단 내가 생각해 본 풀이는 그리디 방식이다. N개의 노드에 N-1개의 간선이 있다면, 루프가 생길 수 없기 때문에 트리 형태가 된다. 1번 노드가 탈출구 이기 때문에 1번 노드를 루트로 선택하면 트리가 형성된다. 간선은 양..

문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 원소가 부분수열에 포함되는지 여부를 경우의 수로 생각해 보자. 포함되느냐 안되느냐인 두 가지 선택을 40개의 수에 적용하면 2^40 가지의 경우가 나온다. 2^40 = 1,099,511,627,776(약 1TB) 이므로 시간 안에 동작시킬 수 없다. 여기서 사용되는 기법이 양방향 탐색(Bidirectional..

문제 https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 가장 큰 수와 가장 작은 수를 만드는 방법을 나누어서 생각해보자. 1. 가장 큰 수 만들기 (그리디) 가장 큰 수를 만들기 위해서는 무엇보다 수의 자릿수를 늘리는 게 최선이다. 예를 들어 성냥개비로 만들 수 있는 가장 큰 한자리 수인 9를 만들기 위해서는 6개의 성냥개비를 써야 한다. 하지만 성냥개비 6개로 1을 3개 만들어 3자리 수 111을 만드는 것..

문제 https://www.acmicpc.net/problem/2494 2494번: 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 역추적의 구현과 숫자 나사의 현재 상태를 구하는 것이 중요했던 DP 문제. 일단, 숫자나사는 최대 10,000개 존재할 수 있기 때문에 왼쪽으로 돌릴때 마다 하위의 나사들을 모두 변형해주는 것은 너무 비효율적이다. 사실 각 나사가 왼쪽으로 회전한 횟수만 알 수 있으면 현재의 상태를 구할 수 있다. 특히, 왼쪽으로 돌리는 것에 영향을 받지 않기..

문제 https://www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 비트 마스킹을 DP에 적용하여 해결하는 문제. 외판원 순회 문제와 굉장히 비슷하니 먼저 풀어보고 오도록 합시다. 이번 문제를 외판원 순회와 같이 해결할 수 있는 이유는 문제를 약간 변형해 보면 알 수 있다. 각 예술가를 도시라고 생각하고 그림의 거래를 외판원이 도시 간의 이동하는 것으로 생각해보자. 외판원 순회 문제에서 1번 -> 2번 -..

문제 https://www.acmicpc.net/problem/11570 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 A(상덕이)가 부른 마지막 음을 a, B(희원이)가 부른 마지막 음을 b라고하자. dp[a][b]에는 a와 b일때의 힘든정도의 최솟값을 저장하자. 이때 현재까지 두 명이 부른 음은 a와 b 중에 더 큰 값(악보상에서 더 뒤에 있는 음)이라고 할 수 있다. (모든 음은 순서대로 불러야 하므로 이는 성립할 수밖에 없다.) 그렇다면 다음으로 불러야 ..

문제 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 연속된 순서의 파일끼리만 합쳐야 한다는 조건이 없다면 우선순위 큐로 간단히 풀 수 있지만, 연속된 파일끼리 합치기 위해 다이나믹 프로그래밍(DP)를 사용해야 한다. dp[start][end]를 start ~ end까지의 파일을 연속되게 합칠 때(하나의 임시 파일로 만들 때) 최소 비용이라고 하자. 이를 구하기 위해서는 start~end 파..

문제 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 자신의 직속 부하가 최고 상관인 서브 트리들에서의 최소 전파 시간을 구한 값을 배열에 저장한다 생각해보자. 부하의 서브 트리들 중에서 가장 전파 시간이 오래 걸리 트리는 언제 방문해야 최단 시간을 구할 수 있을까? 조금만 생각해보면 당연히 전파 시간이 오래 걸리는 순서대로 먼저 방문해야 항상 이득임을 알 수 있다. (오래 걸리는 트리를 늦게 방문할수록 ..

문제 https://www.acmicpc.net/problem/10251 10251번: 운전 면허 시험 만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 참조 풀이 JusticeHui님의 백준10251 운전 면허 시험 풀이 언뜻 보면 최단 거리를 구하는 문제 같지만 사용할 수 있는 연료의 한계가 있기 때문에 풀기 어려웠던 문제. 연료에 제한이 있으면 해당 경로가 최단 경로이라도 연료의 사용량이 많다면 결국에 이용을 못 할 수 있으므로 모든 경우의 수를 생각해보아야 한다. 이때 중요한 것이 모든 도로를 지나는데 걸리는 시간은 L로 동일하고, 방향을..

문제 https://www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 [백준] 고층 빌딩(1328) 문제와 완전히 동일한 풀이로 해결할 수 있다. dp[stick][l][r]를 stick 개수의 막대를 놓았을 때 왼쪽에서 l개, 오른쪽에서 r개가 보이는 경우의 수 라고하자. 모든 막대를 항상 가장 큰 막대부터 작은 막대의 순서대로 놓는다고 생각해보자. 지금까지 stick - 1개의 막대를 놓았다면 다음으로..