백준: 11058 크리보드

문제

11058번: 크리보드

 

문제 풀이

 버튼을 누를 수 있는 횟수 N이 주어질 때, A 버튼, Ctrl-A, Ctrl-C, Ctrl-V를 사용하여 가장 많이 A를 출력하는 횟수를 구하는 문제이다. 주어진 횟수 3, 7, 11의 규칙을 이끌어낼 수 있는 경우의 수를 찾으면 문제를 쉽게 해결할 수 있다.

 

 우선 1에서 6까지는 A를 복사하는 경우보다 A를 입력하는 것이 더 많은 A를 출력할 수 있다. 따라서 1에서 6까지는 A가 출력되는 횟수가 1, 2, 3, 4, 5, 6이다. 하지만 7부터는 복사를 하는 것이 더 많은 A를 출력할 수 있게 된다.

 

 복사를 통해 A가 출력되는 횟수를 늘릴 수 있는 최초의 경우인 7을 생각하면 다음과 같은 경우의 수가 있다.

• A를 3개 출력하고 복사하는 경우
• A를 2개 출력하고 복사하는 경우
• A를 1개 출력하고 복사하는 경우

 따라서 점화식을 `dp[i] = max(dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4)`로 세울 수 있다. 그 후로는 앞의 값을 유지하고 있으므로 해당 점화식을 반복하여 N이라는 횟수가 주어졌을 때, 최대로 출력되는 A를 찾을 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    n = int(stdin.readline())
    dp = [num for num in range(n + 1)]

    for i in range(7, n + 1):
        dp[i] = max(dp[i - 3] * 2, dp[i - 4] * 3, dp[i - 5] * 4)

    print(dp[n])