https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net dp 문제다. 완전 순열로 본인이 본인 것을 선택하는 경우를 제외한 순열이다. n = 2인 경우 a - 2, b - 1 이렇게 한 가지 경우다. n = 3인 경우 a - 2, b - 3, c - 1 a - 3, b - 1, c - 2 이렇게 두 가지 경우다. n = 4인 경우 a - 2, b - 3, c - 4, d - 1 a - 2, b - 4, c - 1, d - 3 a - 2, b - 1, c - 4, d - 3 a - 3, b - 1, c - 4, d - 2 a - 3, b - 4, c - 1, d - 2..
Algorithm/DP
https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net dp문제다. 아이들을 옮기는데 다른 제한이 없으므로 이미 일부분 정렬되어 있는 아이들을 제외하고 움직이는 방법이 최선이다. 증가하는 가장 긴 부분수열을 구하고 전체 수열의 개수에서 부분 수열의 개수를 빼주면 된다. 배열을 순회하면서 해당 숫자를 기준으로 앞 쪽을 탐색한다. 앞 부분 숫자 중 해당 숫자보다 작은 숫자가 있다면 현재 dp배열의 값과 비교한다. if (arr[i] > arr[j]) dp[i] ..
https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net DP 문제다. 그래프 형태의 DP문제로 어떻게 해결할지 고민했다. 처음에는 BFS로 접근을 하였으나 굳이? 싶었고, 시간초과가 날 것 같았다. 두 번째 떠올린 방법은 아래로 움직이는 것은 따로 고려해줄 것이 없으므로 dp[i][j] = dp[i - 1][j]를 해준 후 해당 지점에서 왼 오로 퍼지면서 중복 방문을 방지하도록 했다. 시간 초과를 예상하긴 했지만 반례가 없을 것 같아 시도 했..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net dp 문제 유형 중 하나인 배낭 문제다. 배낭 문제는 물건의 무게와 가치가 주어지고 가방의 무게가 주어졌을 때, 가방에 담은 물건들의 가치가 최대가 되도록 하는 것이다. dp 배열을 가방에 담은 물건의 개수, 가방의 무게 제한에 대한 2차원 배열로 만든다. n개의 물건을 담을 수 있을 때, n번 쨰 물건을 담는다고 생각하자. n번 ..
https://www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수를 구하는 문제다. 쉼터에 도착하면 그 쉼터와 직접 연결된 더 높은 쉼터로 향하는 길들 중 하나를 골라서 그 길을 따라 이동한다. 쉼터의 개수, 쉼터를 연결하는 길의 개수 쉼터의 높이 쉼터를 연결하는 길의 양 끝 쉼터 n번 쉼터에서 출발해서 산을 오를 때 최대로 방문할 수 있는 쉼터의 개수 DP를 이용하여 접근..
https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net DP 문제다. 시작점을 입력에 맞춰 체크해줘야 한다. dp 배열은 시간과 위치로 설정했다. dp 배열을 순회하면서 현재 경험치가 0인 곳은 스킵했다. dp의 칸마다 움직일 수 있는 사냥터를 탐색하여 방학이 지나거나 경험치가 모자라는 경우를 제외했다. 이동하는 경우가 아닌 제자리에 머물러 있는 경우는 따로 고려를 했다. #includ..
