다이나믹프로그래밍1 백준)11052.카드구매하기 - 풀이(JAVA) 처음에는 n보다 작은 자연수들을 더해서 n을 만드는 경우를 구해야 한다고 생각했다. 그런 방향으로 풀다가 시간초과가 나버렸고 구글링 끝에 간단한 방법이 있어 정리해본다. 카드 n개를 구매하는 방법은. n개가 들어있는 팩을 구매하거나, 또는 카드 1개가 들어있는 팩을 구매하고 n-1개가 들어있는 팩을 구매한다. 카드 2개가 들어있는 팩을 구매하고 n-2개가 들어있는 팩을 구매한다. . . . 이런식의 방법이 있다. 가장 큰 비용으로 n개를 구매하는 방법까지 도달하기 전에 n보다 작은 카드들을 가장 큰 비용으로 구매하는 법들을 기억(memomemoization)해놓고, 이전에 구했던 값들을 이용해 n개를 가장 큰 비용으로 구매하는 법을 구하는 방식으로 접근해야 하는 문제다. (Dynamic Programmi.. 2020. 10. 26. 이전 1 다음