[백준 - Python] 11058 - 크리보드

0.  문제 링크

 

 

 

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

11058번: 크리보드

---

1.  풀이 방법

 

 

 

문제에서 파악을 잘 해야 하는 것이, 전체 선택 -> 복사 -> 붙여넣기 과정은 한 번에 수행되어야 한다.

그리고 만약 buffer에 1보다 큰 값이 들어가있다면, 무조건 붙여넣기를 하는게 이득이다.

그러면 문제는 이제 어디서 전체 선택 -> 복사를 할 것이며, 얼만큼 붙여넣기를 할지 결정하는 것이 중요하다.

잘 생각을 해보자.

i 번째를 버퍼에 넣을지, i + 1 번째를 버퍼에 넣을지, i + 2 번째를 버퍼에 넣을지 결정해야 한다.

그림 이슈 ㅈㅅ;

근데 여기서 i - 6번째는 고려할 필요가 없다. 왜냐? 

i - 6 번째는 이미 i - 3에서 고려가 되었기 때문이다.

즉, 해당 점화식에 따라서 i - 3에는 이미 i - 6이 고려된 값이 들어가 있다는 뜻

그리고 붙여넣기는 항상 4번 이하로 발생한다.

이것은 증명할 수 있다.

buffer에는 어떤 값이 들어가있다고 가정하고, i + 4번째 숫자를 만들 때, 경우의 수를 적어놓았다.

이때 붙여넣기를 4번 하면 n + 4 * buffer가 된다. 이때 다른 경우와 비교를 해보자.

따라서 붙여넣니는 4번 이상 할 필요가 없다

---

2.  코드

 

 

n = int(input())
dp = [*range(0, n + 1)]
for i in range(6, n + 1):
    dp[i] = max(2 * dp[i - 3], 3 * dp[i - 4], 4 * dp[i - 5])
print(dp[n])

아래는 배열을 적게 쓰는 코드, 하나의 배열에서 나머지 연산을 통해 인덱스를 참조한다.

n = int(input())
dp = [*range(0, 6)]
for i in range(6, n + 1):
    dp[i % 6] = max(2 * dp[(i - 3) % 6], 3 * dp[(i - 4) % 6], 4 * dp[(i - 5) % 6])
print(dp[n % 6])

---

3.  마무리

 

 

증명을 하니 굉장히 쉬웠고, 코드도 간결하다