선장 일지

- 초기 코드

  - 기존 피보나치 코드를 활용해서 풀었지만, 시간 초과가 떴다.

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

public class Main {
	
	static int N,num;	
	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());
		
		for (int i = 0; i < N; i++) {
			dp = new int[2];
			num = Integer.parseInt(br.readLine());
			fibonacci(num);
			System.out.println(dp[0] + " " + dp[1]);
		}		
	}
	
	static void fibonacci (int n) {
		if (n==0) {
			dp[0] += 1;
		} else if (n==1) {
			dp[1] += 1;
		} else {
			fibonacci(n-1);
			fibonacci(n-2);
		}
	}
}

- 맞은 코드

  - 기존 피보나치 메소드를 사용하는 것이 아닌, 점화식을 통해서 풀었다.

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

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

- 코드 설명

 - 입력이 양수이며 11보다 작다고해서 하나하나 쓰다가 규칙을 찾게 되었다.

 - 규칙은 배열에 dp[0]=1, dp[1]=1, dp[2]=2를 넣은다음 dp[i] = dp[i-3] + dp[i-2] + dp[i-1]로 각 배열마다 값을 넣어주면 1,2,3의 합으로 표현할 수 있는 수가 나오는 것을 발견하였다.

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

public class Main {
	
	static int N,num;
	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[11];
		
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		
		for (int i = 3; i<11;i++) {
			dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
		}
		
		for (int i = 0; i < N; i++) {
			num = Integer.parseInt(br.readLine());
			System.out.println(dp[num]);
		}
		
	}
}

초기 코드

 - 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]);
		
	}
}