[백준 11058] 크리보드 -JAVA // le_effort//

사용 알고리즘 : DP

 

어렵다...  처음 풀 땐 풀 수 있을 것 같았는데 해도 해도 답이 안 나와서 다른 블로그들 참조해보니 잘못된 방법으로 접근했었다

 

일단 2,3,4 연산은 이어져야 한다. 선택하고 복사하고 붙여 넣고.

 

그래서 N이 6까지는 무조건 i이다.

 

for(int i=1; i<=6; i++) {
            dp[i]=i;
        }

 

왜냐?

선택하고 복사하고 붙여 넣는 것의 최댓값을 구하기 위해선 화면에 최대한 A가 많아야 한다.

두 개를 붙여 넣는 것보다는 세 개를 붙여넣는 게 값이 더 크고 세개를 붙여 넣는것 보다는 네개를 붙여 넣는게 더 크다.

 

그럼 n이 6일 때 까진

A A A 선택 복사 붙여 넣기 를 할 경우

A A A A A A  6개다

 

그래서 1부터 6까지의 값은 미리 채워주었다. 이러한 생각은 도대체 어떻게 하는지 모르겠다 ㅠ

 

그리고 n이 7일 때를 생각해 보자

A A A A 선택 복사 붙여 넣기를 하면

 

A A A A A A A A 총 8개가 나온다

 

이후로도 복사 붙여 넣기를 하면 문제의 1번 버튼 화면에 A를 출력한다  이것은 한 개씩 늘어나니까

더 이상 고려할 필요가 없다.

 

 

문제에 나와있는 힌트인 위 사진을 보자.

 

매 단계마다 선택,복사,붙여 넣기  선택,복사,붙여넣기 이렇게만 할 수 있는것이 아니라

선택 복사 붙여 넣기 붙여넣기 붙여넣기 붙여넣기   이런식으로도 가능하다는 걸 알 수 있다.

 

이제 고려해줘야 할 건

 

 

 

A A A A A A A A A A  x y z q 

이렇게 있을 때

x 선택 y복사 z 붙여넣기 q 붙여넣기 넣기 이런 방법도 있고

y에서 선택 z 복사 q 붙여넣기  이런 방법도 있다.

 

 

for(int i=7; i<=n; i++) {
            for(int j=3; j<=i; j++) {
                long printed = dp[i-j];
                long buf = dp[i-j];
                int v_cnt = j-2;
                dp[i] = Math.max(dp[i],printed+(buf*v_cnt));
            }
        }

 

일단 j가 3부터 시작하는 이유를 알아보자

기본적으로 선택 복사 붙여 넣기는 3개의 버튼을 이용해야 한다.

i가 6일 때까지 값은 위에서 구했으니

 

위 반복문의 제일 첫 번째 실행  i =7   j= 3 일 때

long printed = dp [7-3]

long buf = dp [7-3];

int v_cnt = 3-2;

 

dp [i-j]를 계산하면 dp [4]가 된다.

즉 dp [4]에서 3개의 버튼을 눌렀다고 가정을 하는 것이다.

 

맨 처음 선택 복사 붙여 넣기의 경우

printed = dp [4] (기존 화면 A의 개수)

buf = dp[4] (복사하는 과정)

v_cnt = 1 ( 붙여 넣기)

 

기존 화면 + 복사한 것 = printed + (buf * v_cnt);

 

이 과정을 하면 선택 복사 붙여 넣기가 완료된다

 

그다음 j가 4일 때를 보자

printed = dp [3];

buf = dp [3];

v_cnt = 2;

 

이 과정은 dp [3] + dp [3]*2 

dp [3]에서 복사한걸 계속 붙여 넣는 것이다.

 

이런 식으로 비교를 해주면 된다.

 

순서는 대충 이렇다

 

A A A A 선택 복사 붙여 넣기
A A A 선택 복사 붙여넣기 붙여넣기
A A 선택 복사 붙여넣기 붙여넣기 붙여넣기

 

 

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static int max =1;
    static long dp[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        dp = new long[101];
 
        for(int i=1; i<=6; i++) {
            dp[i]=i;
        }
        
        for(int i=7; i<=n; i++) {
            for(int j=3; j<=i; j++) {
                long printed = dp[i-j];
                long buf = dp[i-j];
                int v_cnt = j-2;
                dp[i] = Math.max(dp[i],printed+(buf*v_cnt));
            }
        }
        for(int i=7; i<=n; i++) {
            System.out.println(dp[i]);
        }
        System.out.println(dp[n]);
    }
}