선장 일지

• 생각

동전을 정렬해준 뒤 가장 큰 M보다 작은 동전부터 맞춰나가며 몇개의 동전이 필요한지 세주면 최소의 동전 수로 M을 맞출 수 있을 것이다. 이 문제에선 오름차순으로 알아서 입력이 되니 뒤의 index부터 확인을 해주면 될 것 같다.

• 코드

정답 코드 : 가장 큰 동전부터 맞는 수만큼 count를 세주어가며 M을 맞춰 나갔다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M, count;
	static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		FindMinCount();
		System.out.println(count);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		count = 0;
		array = new int[N];

		for (int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
		
	}

	public static void FindMinCount() {
		// 가장 큰 돈부터 채워나가면 최소의 동전 수로 원하는 값을 채울 수 있다.
        for(int i = N-1; i>=0; i--){
            if(M>=array[i]){
                count += M/array[i];
                M = M%array[i];
            }            
        }
	}

}

• 생각

PPAP는 P로 바꿀 수 있다. 예) PPPAPAP는 PPPAPAP 굵은 부분을 P로 바꾸면 PPAP가 되니 PPAP 문자열이다.

기본적으로 이렇게 PPAP를 replace시켜 P로 바꿔주면 결과는?? 틀렸다고 뜬다.

이유는 PPAP를 P로 바꾸면서 또다시 PPPAPAP와 같은 문자열이 만들어질 수 있기 때문이다.

생각해낸 다른 방법은 반복문을 돌리면서 PPAP로만 만들어진 문자열인지 체크를 해주어야한다.

풀면서 생각해봤는데 현재까지 풀어본 그리디 문제는 정렬을 하면서 푸는 문제였다. 하지만 이 문제는 정렬을 해버리면 PPAP의 순서를 제대로 알아내기 어렵기 때문에 정렬을 하면 안된다. 그래서 그리디 문제이기보단 문자열 문제느낌이 더 강한것 같다.

• 코드

정답 코드 : 반복문을 돌리면서 PPAP로 만들 수 있는지 체크해 준다.

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

public class Main {
	static String ppap;
	static int count;

	public static void main(String[] args) throws Exception {
		SetData();
		SearchStringPPAP();
		System.out.println(ppap);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		ppap = br.readLine();
		count = 0;
	}
	
    public static void SearchStringPPAP() {
    	for(int i = 0; i < ppap.length(); i++) {
    		if(ppap.charAt(i) == 'P') {
    			count++;
    		} else {
    			// PPAP이면 PPAP는 P로 바꿀 수 있기 때문에 count를 -1만 해준다.
    			if(count >= 2 && ppap.length() > i + 1 && ppap.charAt(i+1) == 'P') {
    				count--;
    				i++;
    			} else {	// 현재 A인데 앞에 PP가 없으면 PPA가 되지 않기 때문에 NP를 출력
    				count = 0;
    				break;
    			}
    		}
    	}
    	
    	if(count == 1)
    		ppap = "PPAP";
    	else
    		ppap = "NP";
    }

}

• 생각

0이 입력될때까지 숫자를 입력한 뒤 해당 수를 짝수 두개의 수로 나누어 떨어진 숫자 두개를 출력하면 된다.

1. 에라토스테네스의 체를 통해 소수를 찾아 둔다.

2. 1부터 반복문을 돌면서 i와 number - i 가 모두 소수이면 출력한다.

• 코드

정답 코드 : 에라토스테네스의 체를 통해 소수를 찾고, 1부터 반복문을 돌면서 i와 number - i 가 모두 소수이면 출력한다.

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

public class Main {
	static int N;
	static boolean[] check;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		check = new boolean[1000001];
        getPrimeNumber();
        sb = new StringBuilder();
        
        while(true) {
            int number = Integer.parseInt(br.readLine());
            if(number == 0) break;
            
            for(int i = 1; i <= number/2; i++) {
                int index1 = i;		// 소수 1
                int index2 = number - i;	// 소수 2
                if(!check[index1] && !check[index2]) {		// 둘 다 소수가 맞으
                    sb.append(number + " = " +index1 + " + " + index2 + "\n");
                    break;
                }
            }
        }
	}
	
    public static void getPrimeNumber() {
		check[0] = check[1] = true;
		for (int i = 2; i <= 1000000; i++) {
			if (check[i] == true) {
				continue;
			}
			// 해당 수로 나누어 떨어지는 수는 소수이므로 true로 check
			for (int j = i + i; j <= 1000000; j+=i) {
				check[j] = true;
			}
		}
    }

}

• 생각

일전에 풀었던 LIS 알고리즘을 사용하여 풀었던 기억이 있어서 풀어보았지만 시간 초과가 나왔다.

DP로 하는 다른 방법이 생각이 나지않아서 코드를 찾아 보았다. mygumi.tistory.com/276를 토대로 이해한 결과로 코드를 작성하였다.

• 코드

정답 코드 : 점화식을 찾은 뒤 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, max;
	static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(N-max);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
        max = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
        	int temp = Integer.parseInt(st.nextToken());
            dp[temp] = dp[temp-1]+1;
            max = Math.max(max, dp[temp]);
        }
	}
}

• 생각

후보자 배열을 만들어 준 뒤 index를 서류 성적, value를 면접 성적으로하면 서류 성적으로 오름차순으로 정렬이 된다. 정렬이 된 상태에서 구해주면 구하긴 쉬워진다.

• 코드

정답 코드 : index를 이용해 오름차순 정렬해준 후 답을 도출.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static int T;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

        T = Integer.parseInt(br.readLine());
        sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            int[] candidates = new int[N + 1];
            for (int j = 0; j < N; j++) {
            	st = new StringTokenizer(br.readLine());
                candidates[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
            }

            int count = 1;
            int interviewRank = candidates[1];

            for (int j = 2; j <= N; j++) {
                if (interviewRank >= candidates[j]) {
                    interviewRank = candidates[j];
                    count++;
                }
            }

            sb.append(count + "\n");
        }
	}
}

• 생각

뒤부터 순회를 하면 max를 구하기 위해 따로 순회할 필요가 없다. 따라서 주식 배열을 돌 때 뒤에서부터 max값을 초기화 시켜주면서 max값이 아니라면 max값에서 현재 index의 주식가격을 빼주면서 반복문을 돌려주면 될 것 같다.

• 코드

정답 코드 : 뒤에서부터 반복문을 돌리는게 핵심인 것 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int T;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
        //Calculate();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = Integer.parseInt(br.readLine());
		sb = new StringBuilder();
		
		for( int i = 0 ; i < T ; i++ ) {
			int N = Integer.parseInt(br.readLine());
			long stocks[] = new long[N];
			st = new StringTokenizer(br.readLine());
			for( int j = 0 ; j < N ; j++ ) {
				stocks[j] = Integer.parseInt(st.nextToken());
			}
			
			long max = 0;
			long answer = 0;
			for( int j = N-1 ; j >= 0 ; j-- ) {
				if(stocks[j] > max) {	// 현재 가격이 지금까지 젤 큰 가격이라면 바꿔줌.
					max = stocks[j];
				}else {
					answer += max - stocks[j];	// 팔았을 때 이득을 더 해줌
				}
			}
			sb.append(answer + "\n");
		}
	}

    private static void Calculate(){
    }
}

• 생각

마지막에 들어갈 수 있는 수는 특정 i의 제곱수이므로 항의 개수는 1개가 늘어나게 된다. 이때 n - i^2중에서 가장 최소에다가 1을 더해주면 된다.

• 코드

정답 코드 : 점화식을 이용해서 풀었다.

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

public class Main {
	static int N;
	static int[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
        Calculate();
		System.out.println(dp[N]);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];
	}

    private static void Calculate(){
        for (int i = 1; i <= N; i++){
            dp[i] = i;
            for (int j = 1; j*j <= i; j++){
                if (dp[i] > dp[i-j*j]+1){
                    dp[i] = dp[i-j*j]+1;
                }
            }
        }
    }
}

• 생각

1이 입력되면 정답 : 0
2가 입력되면 정답 : 2
3이 입력되면 정답 : 6
4가 입력되면 정답 : 18

여기까지 해보면 대충 감이 온다. 3부터 i의값은 i-1값의 3을 곱한 값이다. 한번 확인해보니 정답이 다 떨어져 맞았다.

3을 곱하다보면 숫자가 너무커져 int형을 벗어날 수 있으니 long타입으로 배열을 만들어야한다.

• 코드

정답 코드 : 점화식으로 푼 코드이다.

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

public class Main {
	static int N;
	static long[] array;

	public static void main(String[] args) throws Exception {
		SetData();
        Calculate();
		System.out.println(array[N] % 1000000009);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        N = Integer.parseInt(br.readLine());
        array = new long[33334];
	}

    private static void Calculate(){
    	array[1] = 0;
        array[2] = 2;        

        for (int i = 3; i <= N; i++)
                 array[i] = (array[i - 1] * 3) % 1000000009;
    }
}