[백준 11058번 C++] 크리보드

11058번: 크리보드 (acmicpc.net)

11058번: 크리보드

---

[이해하기]

N=3일 때: 

i) 1번 버튼 3번: AAA

 

N=4일 때 ( N=5일 때도 동일)

i) 1번 버튼 4번 : AAAA

ii) 1번, 2번, 3번, 4번 : AA

 

N=6일 때:

i) 1번 버튼 6번 : AAAAAA

ii) 1번, 2번, 3번, 2번, 3번, 4번: A

 

백준 문제에 [힌트] 칸을 봐야 문제가 제대로 이해가 갔다

힌트 칸 안봤다가 문제 애매하다 생각하고 경우의 수 구하느라 시간날림 ㅡ,.ㅡ

[힌트]
N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다.
N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다.
N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V 를 눌러 27개를 출력할 수 있다.

한번 복사하면 붙여넣기를 계속 할 수 있구나!

 

XXX 난 계속 수학적으로 접근했는 데 이렇게 접근 하면 안됨!!! XXX

DP문제니까 DP식으로 접근하기.. (n-1까지의 최댓값 + n .. 이런)

 

dp[i] 는 dp[i-1], dp[i-2]는 할 수 있는 게 1번 버튼 밖에 없음

dp[i] 는 dp[i-3] 에서 선택, 복사, 붙여넣기를 더 할 수 있다 => dp[i] = dp[i-3] *2

dp[i] = dp[i-4] + 선택, 복사, 붙여넣기, 붙여넣기 가 가능하다 => dp[i] = dp[i-3] * 3

dp[i] = dp[i-5] + 선택, 복사, 붙여넣기, 붙여넣기, 붙여넣기 가 가능하다  => dp[i] = dp[i-3] * 3

 

이 5가지 중에서 가장 큰 것을 선택하면 된다

 

[참고]

(c++)백준 11058번: 크리보드 (tistory.com)

(c++)백준 11058번: 크리보드

근데 여기 코드에서 dp[i-2]는 고려해주지 않는다

이유를 모르겠어서 나는 문제를 풀 때 

dp[i] = max(dp[i - 1] + 1, dp[i-2] + 2); 로 두 개 중 큰 거를 선택해서 dp[i]를 먼저 초기화 시켜줬다.

이렇게 수정해도 맞고, 위 링크 코드도 맞았다

dp[i - 1] + 1 가 dp[i-2] + 2 보다 항상 크니까 이게 성립하는 거겠지!

 

---

[코드]

그렇게 완성된 내 최종 코드는..

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long dp[101];

	cin >> n;
	
	//5번까지는 A를 하나 출력하는게 최대
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	dp[4] = 4;
	dp[5] = 5;
	
	//A를 하나 출력하는 것과 이전에 복사해둔 것을 붙여넣기 하는 것 비교
	for (int i = 6; i <= n; i++) {
		dp[i] = max(dp[i - 1] + 1, dp[i-2] + 2);
		for (int j = 1; j <= i - 2; j++)
			dp[i] = max(dp[i], dp[i - 2 - j] * (j + 1));
	}
	cout << dp[n] << '\n';
	return 0;
}