공부 138일차: 백준 2156번 포도주 시식 자바 java

2156 포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

 

 

 

---

백준 2156번 문제 포도주 시식

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

처음엔 이렇게 풀어서 써봤다

3개를 연속해서 마실 수 없으니 3개째부터는 그림에서처럼

101 (6 13)

011 (10 13)

110 (6 10)

이런 식으로 경우를 나누어서 생각해야 한다

그렇기 때문에 공식이 갈리는 시점은 숫자가 3개부터인 지점이라고 생각해서,

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        // 디버깅 System.out.println("배열 : "+Arrays.toString(arr));
        
        dp[0] = arr[0];
        dp[1] = arr[0]+arr[1];
 
        for(int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+arr[i], ★arr[i-1]+arr[i]★));
            System.out.println("dp["+i+"] : "+dp[i]);
        }
    }
 
}
 

이렇게 코드를 짜봤는데 별로 표시한 부분에서 dp[]가 들어가지 않아 문제였다(예제를 입력해봤을 때 다르게 나옴)

그래서 아예 와인잔이 3개일 때까지는 위에서 구하고, 4개째부터 점화식에 대입하기로 했다

 

import java.io.*;
import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        // 디버깅 System.out.println("배열 : "+Arrays.toString(arr));
        
        dp[0] = arr[0];
        dp[1] = arr[0]+arr[1];
        dp[2] = Math.max(dp[1], Math.max(arr[0]+arr[2], arr[1]+arr[2]));
        
        for(int i = 3; i < n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]));
        }
        System.out.println(dp[n-1]);
        
    }
}
 

그래서 이렇게 짰는데, 배열 인덱스 오류가 떴다

n은 1 이상부터인데 와인잔이 2,3개인 dp[1], dp[2]를 구해놔서 생긴 오류였다

 

우선 점화식은

dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]))

 

 

 

---

정답 인정 코드

---

 

인덱스 예외를 수정하고 정답 인정 받은 코드 1)

import java.io.*;
import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        // 디버깅 System.out.println("배열 : "+Arrays.toString(arr));
        
        // n = 1부터이므로 아래는 무조건 성립
        dp[0] = arr[0];
        // 와인잔이 2개 이상일 때
        if(n > 1) {
            dp[1] = arr[0]+arr[1];            
        }
        // 와인잔이 3개 이상일 때
        if(n > 2) {
            dp[2] = Math.max(dp[1], Math.max(arr[0]+arr[2], arr[1]+arr[2]));            
        }
        
        for(int i = 3; i < n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]));
        }
        System.out.println(dp[n-1]);
        
    }
}

 

dp[i-3]이 있어서 크기를 n으로 두기보다 n+1로 두는 게 코드가 더 간단해질 것 같아서 보완해보았다

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        
        for(int i = 1; i < n+1; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        // n = 1부터이므로 아래는 무조건 성립
        dp[1] = arr[1];
        // 와인잔이 2개 이상일 때
        if(n > 1) {
            dp[2] = arr[1]+arr[2];            
        }
        for(int i = 3; i < n+1; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]));
        }
        System.out.println(dp[n]);
        
    }
}

 

찾아보니 이렇게 푼 분들이 엄청 많았다

그런데 백준에 돌려보니 위의 것보다 8ms 정도 느렸다

근소한 차이긴 하지만.. 이게 개선한 코드인지는 모르겠다

 

 

 

---