선장 일지

• 생각

마지막에 들어갈 수 있는 수는 특정 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;
    }
}

• 생각

bfs 문제이다. 이차원 배열을 한 영역에서 양과 늑대의 수를 비교해주면서 돌면된다.

• 코드

정답 코드 : bfs를 통해 구현한 코드이다.

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

public class Main {
	static int R,C, sheep, wolf;
	static char[][] array;
	static boolean[][] check;
    static int[] x;
    static int[] y;

	public static void main(String[] args) throws Exception {
		SetData();
		bfs(0,0);
		System.out.println(sheep + " " + wolf);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		check = new boolean[R][C];
		array = new char[R][C];
		x = new int[]{-1, 0, 1, 0};
		y = new int[]{0, -1, 0, 1};
		sheep = wolf = 0;
		
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                array[i][j] = line.charAt(j);
            }
        }
		
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(!check[i][j] && array[i][j] != '#')
                	bfs(i,j);
            }
        }
	}
	
	private static void bfs(int a, int b) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {a,b});
     	check[a][b] = true;
        int wolfCnt = 0;
        int sheepCnt = 0;
        while (!queue.isEmpty()) {
        	int location[] = queue.poll();
            int r = location[0];
            int c = location[1];
            if (array[r][c] == 'k') {
                sheepCnt++;
            } else if (array[r][c] == 'v') {
                wolfCnt++;
            }
            for (int i = 0; i < 4; i++) {
                int r2 = r + x[i];
                int c2 = c + y[i];
                if(r2 < 0 || r2 >= R || c2 < 0 || c2 >= C) continue;
                
                if (!check[r2][c2] && array[r2][c2] != '#') {
                    check[r2][c2] = true;
                    queue.offer(new int[] {r2,c2});
                }
            }
        }
        if (sheepCnt > wolfCnt) {
            sheep += sheepCnt;
        } else {
            wolf += wolfCnt;
        }
	}
}

• 생각

일전에 이런 문제를 많이 풀었는데, 푸는 방법은 다양하게있다.

1. LIS 알고리즘(dp보다 빠름) - 가장 긴 증가하는 부분 수열 2 (비슷한 문제를 LIS 알고리즘으로 푼 코드이다.)

2. DP - 가장 긴 증가하는 부분 수열 이전에 비슷한 문제를 DP 알고리즘으로 푼 코드이다.

3. 완전탐색 - 너무 오래걸린다. 시간초과 뜰 확률이 높음.

• 코드

정답 코드 : DP로 구현한 코드이다.

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

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

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

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

		N = Integer.parseInt(br.readLine());
		
		dp = new int[N];
		array = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }
		
	}
	
	private static int DP() {
        int max = 1;
        for (int i = 0; i < N; i++) {
        	if (dp[i] == 0) 
        		dp[i] = array[i];
        	for (int j = 0; j < i; j++) {
        		if (array[i] > array[j]) 
        			dp[i] = Math.max(dp[i], dp[j]+array[i]);
        	}
            if(max<dp[i])
            	max=dp[i];
        }

        return max;
	}
}

• 생각

브루트포스 문제이다. 전체 경우의 수에 대해서 중량 500이 되는지 확인하면 된다.

• 코드

정답 코드 : 백트래킹을 활용하여 풀었다.

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

public class Algorithm {
	static int N, K, answer;
	static int[] array;
	static boolean[] check;

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

	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());
		K = Integer.parseInt(st.nextToken());
		array = new int[N];
		check = new boolean[N];
		answer = 0;
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken()) - K;
		
	}
	
	private static void BackTracking(int count, int sum) {
		// Basecase
		if(count == N) {
			answer++;
			return;
		}
		
		for(int i = 0; i < N; i++) {
			if(!check[i] && sum + array[i] >= 0) {
				check[i] = true;
				BackTracking(count + 1, sum + array[i]);
				check[i] = false;
			}
		}
	}
}

• 생각

베스킨라빈스 31의 필승 방법은 30을 외치는 것이다.

30, 26, 22, 18, 14, 10, 6, 2 이렇게 외치면 이길 수 있다. 여기서 찾을 수 있는 것은

30, 30 - 4, 30 - 4*2, 30 - 4*3 .....를 보면 30에서 4의 배수로 빼주면 이길 수 있는 것을 알 수 있다.

여기서, 4의 배수는 3 + 1이다. 여기서 또 3은 베스킨라빈스 31의 규칙인 최대로 말할 수 있는 개수이다.

이걸 토대로 코딩을 구현하면 될 것 같다.

• 코드

정답 코드 : 베스킨라빈스 31의 규칙을 찾아서 풀어낸 코드이다.

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

public class Main {
	static int A;
	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));
		A = Integer.parseInt(br.readLine());
		sb = new StringBuilder();

		for(int i = 1; i <= A; i++) {
			if(30 % (i+1) == 0)		// 내가 30을 부를 수 있으면 필승
				sb.append(i+"\n");
		}
	}
}

• 생각

한쌍씩 곱한 숫자를 모두 다 더한 값을 출력하면 되는 문제이다.

• 코드

정답 코드 : count를 통해 그전까지의 수들을 더해주면서 다음 index에 곱해준다. (모든 쌍의 곱을 더하기 위함.)

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

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

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

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

		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
	}
	
    private static int ReturnMaxValue()   {
        int sum = 0, count = array[N-1];
        for(int i = N-1; i > 0; i--) {
        	sum += count*array[i-1];
        	count += array[i-1];
        }
        
        return sum;
    }
}

• 생각

끝난 시간이 빠를 수록 다음 시작 시간이 빠르기 때문에 정렬이 필요.

내가 쓴 정렬 방법은 종료시간 정렬 후 종료 시간이 같은 경우에 시작시간에 따라 정렬했다.

• 코드

정답 코드 : 정렬 후 회의실 최대 개수를 구해줌.

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

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

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

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

		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			array[i][0] = Integer.parseInt(st.nextToken());
			array[i][1] = Integer.parseInt(st.nextToken());
		}
		
        Arrays.sort(array, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int result = o1[1] - o2[1];
                if (result != 0) return o1[1] - o2[1];	//종료시간에 따라 정렬
                return o1[0] - o2[0];		 //만약 비교하는 값의 종료시간이 같을 경우 시작시간으로 정렬
            }
        });
	}
	
    private static int ReturnMaxMeetingRoom()   {
        int count = 0;    // 최대값 변수 
        int temp = -1;    // 다음시작 시간과 비교할 변수
        for (int i = 0; i < N; i++) {
            //현재 시작시간이 이전 종료시간보다 늦을 경우 
            if (array[i][0] >= temp) {
                temp = array[i][1];
                count++;
            }
        }
        return count;
    }
}