개발하지연

문제 심마니 영재는 산삼을 찾아다닌다. 산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다. 마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다. 점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다. 각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다. 매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다. 에너지를 최대한 아껴야 하..

문제 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이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 기록 (dp 8일차) 이번 dp문제는 재귀로 구현해보았다. 반복문으로 어떻게 할지 모르겠어서 재귀로 했는데 역시 의미적으로 점화식 이해하기는 더 쉬운 것 같다. 런타임에러는 ..

문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 기록 (dp 8일차) 갑자기 하기 싫어서 대충하다가 별 에러 다 났다. 풀이는 n을 만들 수 있는 최소 동전개수 dp배열을 만들어, dp[n] = min(dp[i], dp[i-1원]+1, dp[i-5원]+1, dp[i-10원]+1, , ,) 이런 식으로 모든 동전을 추가해보며 최솟값을 찾아 dp를 갱신한다. 코드 from sys import stdin n, k = map(int, stdin.readline().split()) coins = [..

문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 기록 (dp 8일차) 코드 더 짧고 간단하게 하고 싶어서 두 번 제출했다. 이 문제는 동전들의 조합을 세야되는 문제이기 때문에 coin 순서대로 경우의 수를 계산했다. n원의 동전 조합의 경우의 수를 저장하는 dp배열을 사용하여, coin 별로 dp[n]+=dp[n-coin]을 계산하여 저장했다. 코드 from sys import stdin n, k = map(int, stdin.readline().split()) dp = [0]..