DP2 [BOJ] 2293번 동전1 파이썬 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이 #dp 전체 문제인 k원을 구성하는 경우의 수를 구하는 것을 i원을 구성하는 경우의 수를 구하는 것으로 나누고, 이를 또다시 c원을 사용하는 경우에 i원을 구.. 2022. 8. 10. [BOJ] 1789번 수들의 합 파이썬 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 풀이 #dp 처음에 dp배열에 합들의 값을 저장해줬었는데 그렇게 하니 메모리초과가 났다. 그래서 그냥 sum 변수에 값을 저장하는 방식으로 바꿔 풀었다. 가장 많은 개수의 자연수의 합이 되어야 하기 때문에 가장 잘잘하게(?) 합이 구성되어야 한다. 그렇기 때문에 1부터 더해줘야 한다고 생각을 했고, 이렇게 작은 수부터 더했을 때 sum이 S의 이상이 되면 그 인덱스 값을 저장했다. S와 같은 경우에는 index값이 정답이 되고 S 초과한 경우 딱 초과한 수만큼의 수를 1개 빼주면 .. 2022. 8. 8. 이전 1 다음