[백준 11058] 크리보드

https://www.acmicpc.net/problem/11058 문제이해 총 4가지 조건만을 사용해서 화면에 출력된 A의 개수를 최대로 하는 프로그램을 작성하시오. 풀이 백준 14226의 문제와 비슷하다는 생각이 들어서 그때의 기억으로 BFS로 풀어볼까 했으나 모든 경로를 탐색했다간 4의 100제곱의 연산이 필요해 바로 생각을 접고 예제 입력에 나오는 예제들을 하나씩 직접 풀어봤다.

그 결과 복사한 것을 계속 붙여 넣다가 적절히 큰 수가 되었을 때 다시 복사해서 붙여 넣는 방법으로 정답을 구해야 한다는 것을 알았고 DP로 접근해 봤다. 코드 import sys N = int(sys.stdin.readline()) dp = list(i+1 for i in range(100)) for i in range(len(dp)): k = 2 for j in range(i+3, len(dp)): dp[j] = max(dp[i]*k, dp[j]) k += 1 print(dp[N-1]) 후기 예제...