[BOJ] 11052번 - 카드 구매하기

---

문제설명

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

사고과정

• 경우의 수를 어느정도 나열해서 규칙을 발견하려 했는데 파악하지 못했다..뭔가 숨은 그림찾기 하는 느낌이다..
• 바로 1번의 loop로 해결할 수 있지 않을까 했는데, n이 증가할 수록 비교하는 경우의 수가 많아짐에 따라 2중 루프를 사용했다.
• 예를 하나 들어보자.
  • dp[1] 은 1번 카드 1개를 쓰는 방법만 있다.
  • dp[2] 는 1번 카드를 2번 or 2번 카드를 1번 쓰는 방법만 있다.
  • dp[3] 은 3번 카드 1번 or dp[1], dp[2]를 쓰는 방법 중 하나이다.
  • dp[4] 는 4번 카드 1번 or dp[3], dp[1] 을 쓰는 방법 or dp[2]를 2번 쓰는 방법 중 하나이다.
  • 이렇게 계속적으로 n까지 증가하다 보면
  • dp[n] 은 n번 카드 1번 or dp[1], dp[n-1] or dp[2], dp[n-2] , .... , dp[i], dp[n-i] 중 하나일 것이다.
  • 따라서 n이 증가함에 탐색하는 경우의 수가 많아진다.
• 참고한 풀이는 여기를 살펴보자.

풀이(스스로 못 푼 풀이)

n = int(input())
card = [0] + list(map(int, input().split()))
dp = [0] * (n+1)
dp[1] = card[1]
dp[2] = max(card[2], card[1]*2)

for i in range(3, n+1):
    # i개 들어있는 카드팩 사용
    dp[i] = card[1]
    # 다른 카드팩 고르는 경우 탐색
    for j in range(1, i//2 + 1):
        dp[i] = max(dp[i], dp[j] + dp[i-j])

print(dp[n])