게임 개발 블로그

문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 풀이 사실은 못풀었다! ^___^ 처음에 2x1, 1x2 타일로 3xN 의 타일을 채우는 경우의 수를 생각해 봤는데... 이렇게 5개가 있을 거라고 생각했다. 그래서 N이 2인 형태가 3개. 4인 형태가 2개라고 생각해서 점화식이 dp[n] = dp[n-2] *3 + dp[n-4] *2 일거라고 생각했다. N= int(input()) dp=[0]*31 dp[2] = 3 dp[4] = 11 for i in range(5,N+1): dp[i] = dp[i-2] *3 +dp[i-4] *2 print(d..

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 풀이 자연수 N을 제곱수의 합으로 나타내야 하므로 최소 개수의 제곱수로 표현하기 위해서는 n보다 작으면서 제곱수 만큼 작은 수들 중에서 dp가 가장 작은 수를 구하면 될 것이다. 예를 들어 11의 최소 제곱수의 합을 구하려면 dp[11-9] , dp[11-4], dp[11-1] 에서 가장 작은 수를 택해서 1을 더하면 된다. 문제는 N이 커지면서 ..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 dp[n] : n번째까지의 계단 최댓값으로 설정하고 dp테이블을 채웠다. 최대 다음다음 계단까지 갈 수 있기 때문에 현재의 dp[n]은 1) dp[n] = dp[n-2] + A[n] 2) dp[n] = dp[n-1] + A[n] 둘 중 하나가 될 것이다. 그런데 연속해서 3개의 계단을 밟을 수 없기 때문에 이전 선택에서 2번을 선택했다면 무조건 1번을 선택해야 할 것이다. 그런데 또 여기서 반..

문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 처음에는 dp 테이블을 dp[n][m] : n부터 m까지의 합 으로 정의했고 dp[n][m] 이 dp[n+1][m] + 현재 위치의 값 이라는 걸 이용해서 푸는 문제인 줄 알았다.. length = int(input()) A = list(map(int,input().split())) dp =[[-1001 for k in range(length)] for i in range(length)] f..