크리보드
📖문제
크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.
1. 화면에 A를 출력한다. 2. Ctrl-A: 화면을 전체 선택한다 3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다 4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.
✍입력
첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.
💻출력
크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.
풀이과정
N번째의 버튼에서 최대값을 얻기 위해선 이전에 있던 버튼들의 최대값을 활용해야 함으로 Dynamic Programming을 사용해서 풀어보았다.
N<=6 일 경우에는 A만 출력하는 것이 다른버튼을 사용하는 것보다 A의 개수가 많거나 같다. 따라서 N이 1~6일 때까지 경우를 미리 지정해 놓고 동적계획법을 이용했다.
ctrl+v를 해야지만 A의 개수가 많아지기 때문에 이를 이용한 점화식을 사용해서 풀었다.
#include <iostream>
#include <algorithm>
long long dp[100] = { 0 };
using namespace std;
int main() {
long long N;
cin >> N;
dp[0] = 1;
dp[1] = 2;
dp[2] = 3;
dp[3] = 4;
dp[4] = 5;
dp[5] = 6;
for (int i = 6; i < N; i++) {
for (int j = i-3; j>=2 ;j--) {
dp[i] = max(dp[i],(i-j-1)*dp[j]);
}
}
cout << dp[a-1];
return 0;
}
good