다이나믹 프로그래밍

📌 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져..

📌 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 📌 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 📌 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. 📌 문제 풀이 👨‍🏫 접근 문제가 꽤 어려웠다. 조건을 이해하기가 어려웠기 때문이다. 문제를 분석해보자면, 이 게임은 SK의 입장에서 풀이해야 한다. 모든 참가자가 자신이 이길 수밖에 없는 구조로 게임을 하는데, 선공이 ..

📌 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아? 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그..

📌 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 📌 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 📌 출력 첫째 줄에 경우의 수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 재귀를 통해서 완성된 조건을 풀 수 있을 것 같아보였다. 그런데 시간이 좀 오래 걸릴 것 같아서 DP를 사용했다. DP가 사용 가능한 이유는 이전 값을 참고하여 현재의 값을 구할 수 있기 때문이다. 일단 3 X 2의 타일이 있을 때, 위와 같이 3개의 배치가 가능하다. 그 다음 3X3 의 타일 배치를 구하려고 했는데, 절대로 배치를 할 수가 없었다. 직관적으로 생각해보면, 3X3은 9개의 타일이 필요한데, 2X1 타일을 아무리 배치한들 8이라는 짝수로 채워지기 때문에 남은 타일 1개를 절대 ..