[Swift][DP] 백준 11058번 (크리보드)

요구능력 : DP

 

코드설명 : 

 

의식의 흐름대로 문제를 풀게됬다.

일단 2번부터 4번조건은 처음에는 세개가 다같이 발동해야한다.

1번부터 6번까지는 그냥 A를 찍는게 수가 훨씬 많다고 생각해서 dp[i]에 i를 넣어주었다.

그리고 i가 7일때 부터는 전체선택, 복사, 붙여넣기 등의 과정이 들어가는게 A를 더 많이 찍게된다.

n이 7일 때를 가정해서, 점화식을 구해보면

버튼을 총 7번 누를 수 있는데 이 중에서 전체선택, 복사, 붙여넣기를 하려면 버튼 누르는 수가 3번이 있어야한다.

그럼 우리는 A를 최대한 찍고 저 3번을 눌러야한다.

그렇기 때문에 바로 dp[i - 3]인 곳에서 전체선택,복사,붙여넣기를 하면 버튼은 총 7번 누르게된다.

그리고 붙여넣기를 했기 때문에 dp[i - 3]의 A의 개수에서 2배가 된다.

그럼 점화식은 dp[i - 3] * 2가 된다.

 

그런데,

dp[4]는 4인데 * 2하면 8이된다.

문제에서 예시는 7을 넣으면 9가 나온다.

여기서 한가지 빠진 부분이 있다.

바로 버퍼에 복사되어있는 내용은 붙여넣기 버튼 1번만 누르면 A의 개수가 또 늘어난다는 것이다.

dp[7] = dp[3] * 3이라서 9인것이다.

여기서 점화식을 다시 구해보면 아래와 같이 나온다.

dp[i] = dp[i - j] * (j - 1)

 

그런데,

여기서 그냥 저 점화식을 가져다 쓰면 100프로 틀린다.

이유는 dp[i - 3] * 2가 dp[i - 4] * 3보다 큰 경우가 존재할것이기 때문이다.

그래서 max를 통해 기존의 값이 더 크다면 두고 후의 값이 더 크다면 바꿔준다.

 

후기 : 오랜만에 간단한 DP문제를 풀어본것같다.

let n = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: 101)
for i in 1...n{
    if i <= 6 {
        dp[i] = i
    }else{
        for j in stride(from: 3, through: n, by: 1){
            if i - j <= 0 {continue}
            dp[i] = max(dp[i], dp[i - j] * (j - 1))
        }
    }
    
}
print(dp[n])