L.O.K

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ◎ 문제풀이 무게 제한이 있는 배낭에 아이템을 넣는 경우, 가치의 최댓값을 구하는 문제이다. 2가지 경우를 생각할 수 있다. 1) 배낭에 넣는 경우 2) 배낭에 넣지 않은 경우 그래서 DFS로 2가지 경우를 완전 탐색해도 될거 같지만, DP로 문제를 풀어보겠다. 무게 제한이 7인 배낭에 아이템1( 무게 6 ), 아이템2( 무게 4) , 아이템3( 무게 3 ), 아이템4( 무게 5 )를 넣으려고 한다..

1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net ◎ 문제풀이 DP 발상이 가능하면 쉽게 풀 수 있는 문제이다. 어느 한 지점에 도착할 수 있는 경우는 2가지이다. 1) 바로 옆에서 1 이동하는 경우 2) 지름길로 이동하는 경우 지름길로 이동하는 경우는 여러가지가 될 수 있다. 그러므로 여러 가지 경우 중에서 가장 최소인 비용을 기억(메모리제이션) 해놓고 다음 지점의 최소비용 구할 때 사용하면 된다. 0부터 목표지점 D까지 Bottom-Up 방식으로 1씩 dp 값을 구하는 방식으로 문제를 풀면 된다...

17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net ◎ 문제풀이 진우가 지구에서 달까지 높이마다 정해진 방향으로 이동할 때, 비용의 최솟값을 구하는 문제이다. 처음에는 높이마다 정해진 방향으로 이동하므로, 계층에 따른 모든 경우의 수를 완전탐색하는 DFS 알고리즘을 떠올렸다. 그러다가 문제가 탐색(재귀호출)으로 어떤 조합을 찾기보다는 최적해를 구하는 문제이므로, 메모리제이션을 활용한 DP 풀이가 더 적합하다는 생각으로 바뀌었다. 이동에는 3가지 경우가 있다. 1) 좌측 아래로 대각선..

15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net ◎ 문제풀이 문제를 보고 DP를 떠올렸으나 '순서만 다른 것은 같은 것으로 본다'는 조건이 어려웠다. 순서만 다른 정렬을 같게 만들려면 오름차순으로 정렬하면 된다. +1 로 끝난 식 뒤에는 +1만 올 수 있고 +2로 끝난 식 뒤에는 +1, +2만 올 수 있고 +3으로 끝난 식 뒤에는 +1, +2, +3만 올 수 있다. 예를 들어 dp[4][1] : 4를 만드는데 끝이 1인 경우의 수이다. dp[4][2..

11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net ◎ 문제풀이 아직까지는 하나의 알고리즘 문제에 다른 알고리즘이 응용되는 문제를 푸는게 쉽지 않은 것 같다. '파일 합치기' 문제도 DP 알고리즘에 누적합 알고리즘을 적용해야 풀리는 문제이다. 파일은 최종적으로 두개의 묶음으로 합쳐진다. dp[i][j]가 i부터 j까지 묶음의 최대값이라고 해보자. > dp[1][5] = dp[1][1] + dp[2][5] + C1 ~ C5까지의 합 > dp[1][5] = dp[1][3] + dp[4][5] + C1 ~ C5..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net ◎ 문제풀이 처음에는 대부분 DFS로 풀었다가 시간초과를 마주한다. 한 경로가 위처럼 이동했다고 해보자. 경로가 지나간 노드는 모두 방문된 노드가 된다. 보통의 DFS 풀이처럼 한번 방문한 노드를 다시 방문하지 못하도록 조건을 건다면 DFS의 시간복잡도는 O(N+E)가 된다. ( N은 노드의 개수, E은 간선의 개수 ) N은 최대 2,500개이고 간선은 노드 하나당 4개를 갖는다고 가정하면 10,000개이다. 시간복잡도가 O(N+E)면 충분히 시간제한 2초안에 풀 수..

15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net ◎ 문제풀이 DP 점화식 구현이 까다로운 문제였다. 7일에 받을 수 있는 상담의 경우의 수는 다음과 같다. 1일에 시작된 상담이 6일 걸려 7일이 될 수 있고 3일에 시작된 상담이 4일 걸려 7일이 될 수 있다 그리고 만약 전날에 마무리 된 상담비용이 더 크면 그대로 7일의 상담비용이 된다. 이와 같이, 7일이 될 수 있는 모든 경우의 수에서 최댓값을 구하면 된다. ◎ 코드 import java.io.BufferedReader; im..

2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net ◎ 문제풀이 벽돌이 100개 이하로 주어질 때, 벽돌을 쌓아 올릴 수 있는 최대 높이를 구하는 문제이다. 이 문제가 까다로운 이유는 두 개의 조건을 고려해야 하기 때문이다. 1) 밑면의 넓이 2) 무게 이런 경우, 밑면의 넓이로 정렬해준 다음 무게로 DP 풀이를 하면 된다. 먼저, N개의 벽돌을 밑면의 넓이가 작은 순서대로 오름차순 정렬을 한다. 그리고 밑면의 넓이가 작은 것부터 하나씩 DP 테이블을 만들 것이다. DP테이블은 N번째 블록을 가장 밑으로 하는..

1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net ◎ 문제풀이 개인적으로 이렇게 넓은 범위의 경우의 수를 갖는 DP 문제를 푼 것이 처음이기에 풀이를 잘 이어가지 못했다. 볼륨은 매 곡마다 정해진 크기만큼 올리거나 내릴수 있다. 시작볼륨이 5라고 했을때, 곡이 진행되면 진행될수록 그 경우의 수는 2배씩 증가한다. 볼륨의 최대 크기도 정해져 있으니 무조건 매 곡 볼륨을 증가한다고 최대 볼륨이 되는 것 또한 아니다. 모든 경우의 수가 최대 볼륨이 될 수 있는 가능성이 있는 것이..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ◎ 문제풀이 LCS에는 두 가지가 있다. 1) Longest Common SubSequence 2) Longest Common SubString 전자는 공통되는 최장 부분 수열을 구하는 것이고 후자도 공통되는 최장 부분 수열을 구하는 것이지만 연속으로 이어져 있는 부분수열을 구하는 알고리즘이다. 위 문제는 연속으로 이어지지 않고 공통되는 최장부분수열을 구하는 문제이므로, Longest Common SubSequence..