[JAVA] 백준 2156번 : 포도주 시식

 

초기 코드

 - 5개씩 값을 가져와서 문제대로 연속 3개가 나오지 않도록 더해지는 최대 수의 앞쪽 인덱스 3개의 값들만 더해서 total에 더해준다. 이 작업의 for문은 index를 3개씩 증가시킴.

 - 여기서 문제는 가져온 3개의 인덱스가 다음 for문에서 연속 3개가 나오지 않게해야된다. (맨뒤의 인덱스 O X O는 flag를 통해서 막았는데 X O O이렇게 더해준경우를 생각하지 못했다.)

 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
    	Scanner scanner = new Scanner(System.in);
        
    	int X = scanner.nextInt(); //정수 값 받아옴
    	int[] array = new int[X+4];		//배열 선언
    	
    	for(int i = 0; i<X;i++) {
    		array[i] = scanner.nextInt();
    	}
    	
    	int total = 0;
    	boolean flag = true;
    	for(int i = 0; i<X;i=i+3) {
    		int total1 = 0;
    		int max = 0;
    		
    		if (total1 < array[i]+array[i+2]+array[i+4]) {
    			total1 = array[i]+array[i+2]+array[i+4];
    			max = array[i]+array[i+2];
    			flag = false;
    		}
    		
    		if (flag && total1 < array[i] + array[i+1] + array[i+3] + array[i+4]) {
    			total1 = array[i] + array[i+1] + array[i+3] + array[i+4];
    			max = array[i] + array[i+1];
    			flag = true;
    		}
    		if (total1 < array[i] + array[i+2] + array[i+3]) {
    			total1 = array[i] + array[i+2] + array[i+3];
    			max = array[i] + array[i+2];
    			flag = false;
    		}
    		if (total1 < array[i+1] + array[i+3] + array[i+4]) {
    			total1 = array[i+1] + array[i+3] + array[i+4];
    			max = array[i+1];
    			flag = true;
    		}
    		if (total1 < array[i+1] + array[i+2] + array[i+4]) {
    			total1 = array[i+1] + array[i+2] + array[i+4];
    			max = array[i+1] + array[i+2];
    			flag = false;
    		}
    		total += max;
    	}
    	
    	System.out.println(total);
	}
}

 

 

중간 코드

- 위의 X O O를 고른 경우까지도 막았다. 제출해봤는데 틀렸다고한다. 반례 모두 다 잘 되는데 어디가 틀렸을까... 코드가 더럽다.. 맞춘다음에 바꿔보고싶다.. 어디가 틀린걸까..?

 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
    	Scanner scanner = new Scanner(System.in);
        
    	int X = scanner.nextInt(); //정수 값 받아옴
    	int[] array = new int[X+4];		//배열 선언
    	
    	for(int i = 0; i<X;i++) {
    		array[i] = scanner.nextInt();
    	}
    	
    	int total = 0;
    	boolean flag = true;
    	boolean flag2 = true;

    	for(int i = 0; i<X;i=i+3) {
    		int total1 = 0;
    		int max = 0;
    		
    		if (flag2 && total1 < array[i]+array[i+2]+array[i+4]) {
    			total1 = array[i]+array[i+2]+array[i+4];
    			max = array[i]+array[i+2];
    		}
    		
    		if (flag2 && flag && total1 < array[i] + array[i+1] + array[i+3] + array[i+4]) {
    			total1 = array[i] + array[i+1] + array[i+3] + array[i+4];
    			max = array[i] + array[i+1];
    		}
    		if (flag2 && total1 < array[i] + array[i+2] + array[i+3]) {
    			total1 = array[i] + array[i+2] + array[i+3];
    			max = array[i] + array[i+2];
    		}
    		if (total1 < array[i+1] + array[i+3] + array[i+4]) {
    			total1 = array[i+1] + array[i+3] + array[i+4];
    			max = array[i+1];
    		}
    		if (total1 < array[i+1] + array[i+2] + array[i+4]) {
    			total1 = array[i+1] + array[i+2] + array[i+4];
    			max = array[i+1] + array[i+2];
    		}
    		
    		if (total1 == array[i]+array[i+2]+array[i+4]) {
    			flag = false;
    			flag2 = true;
    		}
    		
    		if (total1 == array[i] + array[i+1] + array[i+3] + array[i+4]) {
    			flag = true;
    			flag2 = true;
    		}
    		if (total1 == array[i] + array[i+2] + array[i+3]) {
    			flag = false;
    			flag2 = true;
    		}
    		if (total1 == array[i+1] + array[i+3] + array[i+4]) {
    			flag = true;
    			flag2 = true;
    		}
    		if (total1 == array[i+1] + array[i+2] + array[i+4]) {
    			flag = false;
    			flag2 = false;
    		}
    		
    		total += max;
    	}
    	
    	System.out.println(total);
	}
}

 

- DP 에 대해 배운 뒤 고친 코드

 - 맞았다고 잘 뜬다. arr 배열과 dp배열을 이용해 앞에서부터 차근차근 풀어나가는 dp 방식으로 풀었다.

 

import java.util.Scanner;

public class Algorithm {
    public static void main(String args[]) {
    	Scanner scanner = new Scanner(System.in);
        
    	int X = scanner.nextInt(); //정수 값 받아옴
    	int[] dp = new int[X+3];		//배열 선언
    	int[] arr = new int[X+3];
    	
    	for(int i = 3; i<X+3;i++) {
    		arr[i] = scanner.nextInt();
    	}

        for (int i = 3; i < X+3; i++) {
            dp[i] = Math.max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]);
            dp[i] = Math.max(dp[i-1], dp[i]);
        }
    	
    	System.out.println(dp[X+2]);
	}
}

 

- 다른 사람들의 코드

  - 메모리, 시간 모두 1/2인 사람들이 있길래 어떻게 하는건가 보고 내꺼랑 비슷하게 바꿔봤는데 메모리랑 속도가 확실히 빠르게 된다 왜그렇지?? 

 

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

public class Algorithm {
	
	static int N;
	static int[] arr;
	static int[] dp;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		dp = new int[N+3];
		arr = new int[N+3];
		
		for (int i = 3; i < N+3; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
        for (int i = 3; i < N+3; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]));
        }
		
		System.out.println(dp[N+2]);
		
	}
}