[백준] code.plus(다이나믹 프로그래밍,JAVA)11058번, 크리보드

문제 링크

11058번: 크리보드

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

이 문제에 핵심은

 

1. 크리보드에 버튼을 N번 눌러서 A를 출력할 수 있는 최대 개수를 결과로 출력합니다.

2. 크리보드에는 문제에서 설명하는 4가지 기능이 존재합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 N을 저장합니다.

 

2. 크리보드의 기능을 사용하는 경우를 탐색하여 1..n번 눌렀을 때 최대값을 DP[1...n]에 저장합니다.

 

3. DP[n]의 값을 결과로 출력합니다.

 

 

DP[i]의 형태

 

크리보드 버튼을 i번 눌러서 A의 최대 출력 개수를 저장합니다.

 

 

크리보드의 기능을 사용하는 경우

 

크리보드를 현재 A의 개수를 복사하려면 Ctrl+A -> Ctrl+C -> Ctrl+V로 3번을 눌러야 합니다.

 

문제에서는 최대 A의 개수를 구해야하기 때문에 Ctrl+V를 누르는 것도 현재 화면에 최대 3번까지 해야합니다.

 

Ex.

 

AAA : 3

 

Ctrl+A -> Ctrl+C -> Ctrl+V

AAAAAA : 6

 

Ctrl+V

AAAAAAAAA : 9

 

Ctrl+V

AAAAAAAAAAAA : 12

 

여기서 Ctrl+V를 반복하는 것보다

다시 Ctrl+A -> Ctrl+C -> Ctrl+V을 진행하는 것이 더 A를 많이 출력할 수 있어서 최대 3번까지 가능합니다.

 

Ctrl+V -> Ctrl+V -> Ctrl+V

AAAAAAAAAAAAAAAAAAAAA : 21

 

Ctrl+A -> Ctrl+C -> Ctrl+V

AAAAAAAAAAAAAAAAAAAAAAAA : 24

 

 

예제입력 1.

 

1. 입력되는 N을 저장합니다.

 

n = 7

 

2. 크리보드의 기능을 사용하는 경우를 탐색하여 1..n번 눌렀을 때 최대값을 DP[1...n]에 저장합니다.

 

DP[1....6]은

Ctrl+A -> Ctrl+C -> Ctrl+V = 화면에 A를 출력하기 

화면에 A를 출력하기를 눌렀다고 판단하였습니다.

 

DP[1] = 1

DP[2] = 2

DP[3] = 3

...

DP[6] = 6

 

DP[7]

 

Ctrl + V를 1번(Ctrl+A -> Ctrl+C -> Ctrl+V)

복사되는 A는 개수 DP[7 - 3]

DP[4] * 2 = 8

 

Ctrl + V를 2번(Ctrl+A -> Ctrl+C -> Ctrl+V -> Ctrl+V)

복사되는 A는 개수 DP[7 - 4]

DP[3] * 3 = 9

 

Ctrl + V를 3번(Ctrl+A -> Ctrl+C -> Ctrl+V -> Ctrl+V -> Ctrl+V)

복사되는 A는 개수 DP[7 - 5]

DP[2] * 4 = 8

 

 

3. DP[n]의 값을 결과로 출력합니다.

 

 

DP[7] = 11

 

DP[7]를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 2중 for문을 통해서 복사 최대 3번까지 진행되도록 하여 DP[1..n]의 값을 저장하였습니다.
• DP[n] 값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
public class Main {
    static int N;	//버튼 누르는 횟수
    static long[] DP;	//n번 눌렀을 때 A를 최대로 출력하는 개수 저장하는 메모이제이션 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        DP = new long[N+1];
        //DP[1...n]의 값 저장하기
        for(int i=1;i<=N;i++){
            DP[i] = DP[i-1] + 1;
            if(i>6){
                for(int j=3;j<=5;j++){
                    DP[i] = Math.max(DP[i], DP[i-j] * (j-1));
                }
            }
        }
        bw.write(DP[N] + "");	//DP[n]의 값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}