BOJ : 11058

1. 문제

 

2. 문제 분석 및 알고리즘 설계

 

입력 | (드래그, 복사, 붙여넣기) | 붙여넣기

이렇게 3가지 경우로 나누어서 생각해야하는 문제이다.

그래서 1~6까지는 입력만 하는 경우가 최대이다.

하지만 7부터는 드복붙의 위치를 바꿔가면서 생각해봐야 한다.

이런 유형을 풀때는 그래도 몇 10개 정도의 경우의 수를 적으면서 생각하는 것을 추천합니다!!

ex) A = 7

      j가 3부터 시작인거는 드복붙이 세트라서입니다!!

      () 소괄호 안은 입력&드복 후 붙여넣기 횟수입니다!!

      입입입입드복붙 ▶︎ dp[7-3] * (3-1) = 8

      입입입드복붙붙 ▶︎ dp[7-4] * (4-1) = 9 (최대)

      입입드복붙붙붙 ▶︎ dp[7-5] * (5-1) = 8

      입드복붙붙붙붙 ▶︎ dp[7-6] * (6-1) = 5

for(int i=7;i<=N;i++){
      for(int j=3;j<i;j++){
             dp[i] = Math.max(dp[i], dp[i-j]*(j-1));
      }
}

 

3. 코드

package week7;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q11058_boj {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long dp[] = new long[N+1];

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

        for(int i=7;i<=N;i++){
            for(int j=3;j<i;j++){
                dp[i] = Math.max(dp[i], dp[i-j]*(j-1));
            }
        }

        System.out.println(dp[N]);
    }
}

 

4. 시간복잡도

 

O(n^2)

 

5. 결과

 

6. 틀린 이유

 

dp 초기값 선언할때 처음에 N+1로 했는데 자꾸 ArrayIndexOutOfBounds 오류가 나서 그냥 100까지 라길래 101까지 잡았습니다.

아 1~6까지 값때문이네요.. 창피하군요

 

7. 소감

 

처음에 감이 잘 안잡혀서 손으로 많이 적으면서 풀다보니 문제에 대한 이해가 잘된 것 같습니다. 오류가 왜 났을까요? 창피하군요2