https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DP와 DFS 문제다. DFS를 통해 경로를 탐색하고, 돌아오는 길에 경우의 수를 저장해 값이 존재하는 경우 더 탐색하지 않는 DP를 이용한다. DFS의 return 조건은 도착지에 도달 했을 떄, 이미 방문한 적이 있을 때다. 모든 경로의 전체를 탐색하면 당연히 시간초과가 나기 때문에 이미 방문한 적이 있을 경우에는 탐색을 멈춘다. 탐색을 멈추고, 해당 칸에 저장된 값을 현재 칸에 더한다. 그렇게 쭉..
Algorithm/DP
https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net DP와 Greedy 문제다. 제한된 성냥개비를 모두 이용하여 만들 수 있는 가장 작은 수와 가장 큰 수를 찾는 문제다. 자릿수가 커질 것이기 때문에 숫자가 아닌 문자열을 이용해 계산했다. 가장 큰 수의 경우 자릿수를 제일 크게 늘려야 한다. 1을 만들 때 2개가 필요하고 7을 만들 때 3개가 필요하므로 두 개만을 이용해 홀수 짝수인 경우를 고려했다. dp[2] = "1", dp[3] = "7" 만 초기값..
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP 문제다. 파일을 합치는 데는 두 파일의 무게의 합 만큼의 비용이 들고, 이 비용을 최소화 하는 문제다. 파일을 합칠 때는 연속한 두 개를 선택하여 합칠 수 있다. 처음 생각한 방법은 1차원 배열을 이용해 최소의 비용을 찾아나가는 것이다. 1번 파일부터 n-1번 파일까지 고려된 최소 비용에 n번 파일을 합치는 비용을 고려했다. 1 2 3 4 라는 파일이 있는 경우 3까지 계산이 됐다고..
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 원형 칸에서 나란하지 않은 k개를 고르는 경우의 수를 구하는 문제다. 몇가지 계산하다보니 바로 규칙을 찾을 수 있었다. 행이 n, 열이 k일 때 아래와 같은 표를 그릴 수 있다. 1 2 3 4 4 4 2 0 0 5 5 5 0 0 6 6 9 2 0 7 7 14 7 0 표를 통해 dp[i][j] = dp[j - 1][i] + dp[j - 2][i - 1]와 같은 점화식을 세울 수 있다. #include usi..
[https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net DP와 누적합 문제다. 해당 칸을 기준으로 왼쪽 위쪽으로 존재하는 숫자들의 개수를 세어 배열에 저장한다. 배열은 3차원 배열로 행렬크기에 1~10의 개수를 각각 저장할 수 있는 11의 크기다. 검정색 부분까지의 누적합을 구하기 위해서는 빨간 부분 + 파란 부분 - 보라 부분을 해야한다. 빨간 부분에도 파란 부분에도 보라 부분이 포함되어 있기 때문에 중복 계산되므로 한 번 빼야..
https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net DP와 누적합 문제다. 불도저가 왼쪽 위에서 오른쪽 아래까지 가는 길에 아래 부분은 사과가 많도록 윗 부분은 바나나가 많도록 지나가야 한다. 불도저는 오른쪽, 아래쪽, 오른쪽 아래 대각선으로 움직일 수 있다. 열을 기준으로 생각을 했다. 아래로 가는 경우에는 아래 칸이 사과인지만 확인해서 빼주면 되고 오른쪽 혹은 대각선으로 움직이는 경우는 그 열에 대해 위의 바나나나 아래 사과만 확인해주면 된다..
