[BOJ] 백준 11058번 크리보드 (Java)

#11058 크리보드

난이도 :  골드 5

유형 : DP

11058번: 크리보드

▸ 문제

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

▸ 출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

 

 

문제 풀이

주어진 버튼 횟수로 A를 최대로 출력하는 횟수를 구하는 문제이다. 각 경우의 수를 모두 따져보고 점화식을 생각해내어 풀면 된다.

 

📚 조건

   ∙ 버튼 누르는 횟수 N ( 1 <= N <= 100)

   ∙ 버튼 역할 총 4가지

       1) 화면에 A 출력

       2) Ctrl-A : 화면 전체 선택

       3) Ctrl-C : 전체 선택한 내용을 버퍼에 복사

       4) Ctrl-V : 버퍼가 비어있지 않은 경우, 화면에 출력된 문자열의 바로 뒤에 버퍼 내용 붙여놓음

 

 

일단 복사-붙여넣기를 하려면 최소 3번의 버튼을 눌러야한다. 선택 > 복사 > 붙여넣기

그래서 N이 1~6일 때는 그대로 A를 출력하는 것이 최댓값을 가진다.

 

그럼 이제 점화식을 만들어보자.

 

1) 메모이제이션할 변수는 버튼을 누르는 횟수 1개이고 배열 안에 그 횟수안에 출력할 수 있는 A의 최댓값을 담으면 된다.

  ☛ 1차 배열 dp[i] , i : 버튼 누른 횟수 

 

2) 반복문 루프를 하면서 i가 7이상일 때부터는 복사 붙여넣기의 경우의 수를 고려하여 값을 비교해서 최댓값을 갱신해준다.

비교는 간단하게 생각하면 된다.

 

버튼 3회를 누르면 값이 dp[i-3]의 2배로 복사된다. 4회를 누르면 3배, 5회 4배, ..., j회 누르면 j-1배 복사된다.  dp[i] = dp[i-j]*(j-1)

dp[i] = Math.max(dp[i], dp[i-j]*(j-1));

 

3) 점화식 반복문의 범위는 i : 1~n번까지 조회하고, 복사값의 비교는 i>6일 때, j : 3~5까지만 비교해줘도 된다.

이미 dp[0~i]는 최댓값으로 갱신된 값들이기 때문에 모든 값을 비교할 필요없고 새롭게 복붙을 할 수 있는 3회부터 다음 복붙이 가능한 6회 전까지만 비교해줘도 된다.

 

  dp[i] = dp[i-1] +1;   : 기본적으로 화면 A출력을 하면 1개씩 추가가 되니 dp[i-1]+1값을 넣어준다.

for(int i=1; i<n+1; i++) {
	dp[i] = dp[i-1]+1;

	if(i>6) {
		for(int j=2; j<5; j++) {
			dp[i] = Math.max(dp[i], dp[i-(j+1)]*j);
		}
	}
}

 

풀이 코드  

import java.io.*;

public class Main {
	static long[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dp = new long[n+1];
		
		for(int i=1; i<n+1; i++) {
			dp[i] = dp[i-1]+1;
			if(i>6) {
				for(int j=2; j<5; j++) {
					dp[i] = Math.max(dp[i], dp[i-(j+1)]*j);
				}
			}
		}
		System.out.println(dp[n]);
	}
	
}

 

 

+

🐻 만약 점화식으로 잘 안풀린다면 Top-down으로 풀어도 된다. 확실히 재귀호출방식이 더 직관적이라서 구현하기 쉽다.

import java.io.*;

public class Main {
	
	static long[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dp = new long[n+1];
		System.out.println(solve(n));
	}
	
	// top-down
	static long solve(int idx) {
		if(idx <= 0) return 0;
		if(idx ==1) return dp[idx] = idx;
		if(dp[idx] >0) return dp[idx];
		
		dp[idx] = solve(idx-1) +1;
		for(int i=2; i<5; i++) {
			dp[idx] = Math.max(dp[idx], solve(idx-(i+1))*i);
		}
		return dp[idx];
	}
}