선장 일지

• 생각

1. 이런 문제들은 대부분 규칙이 있다. 

위의 사진으로 보면 이해가 잘 될 것이다. 5의 배수마다 0의 count 값이 증가하는 것을 볼 수 있다. 

근데 중요한 점은 입력값이 25일 때 1씩 증가하던 count 값이 2가 증가한다.

이유는 뒷자리가 0이 n개 있다는 의미는 2와 5개 n개씩 짝지어 존재한다는 것이다.

팩토리얼 값을 보면 2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스럽게 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

즉, 기본적으로 5의 개수에 따라 값이 변화한다고 볼 수 있다. 

• 코드

정답 코드 : 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누면서 누적합을 구해주면 된다.

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

public class Algorithm {
	static int N;

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

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

	private static int CountZero() {
		int count = 0;
		while (N >= 5) {
			count += N / 5;
			N /= 5;
		}

		return count;
	}
}

• 생각

 nCm이 뭐였는지 기억이 잘 나지않아서 풀어보게 되었다.  nCm => n! / (n-m)!m! 라고 보면 된다.

1. 재귀로 풀어질 것 같다.(long타입으로도 범위를 받아들일 수 없다고함. ==>> BIgInteger 사용 해야함) ==>> 시간 초과

• 코드

정답 코드 : 핵심은 long타입도 범위를 받아들일 수 없기 때문에 BigInteger을 사용하는 것이다. 

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

public class Main {
	static int N, M;

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

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

	private static BigInteger Combination() {
		BigInteger num1 = BigInteger.ONE;
		BigInteger num2 = BigInteger.ONE;
		for (int i = 0; i < M; i++) {
			num1 = num1.multiply(new BigInteger(String.valueOf(N - i)));
			num2 = num2.multiply(new BigInteger(String.valueOf(i + 1)));
		}

		return num1.divide(num2);
	}
}

• 생각

1. 입력으로 N이 주어지고, 출력으로 N자리 3의 배수의 개수를 출력해주면 되는 간단한 문제 첫번째 자리엔 0이 올 수 없고 0, 1, 2 차례대로 넣어주면 된다.

• 코드

정답 코드 : 입력으로 N이 주어지고, 출력으로 N자리 3의 배수의 개수를 출력해주면 되는 간단한 문제 첫번째 자리엔 0이 올 수 없고 0, 1, 2 차례대로 넣어주었다.

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

public class Main {
	static int N, count;

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

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        N = Integer.parseInt(br.readLine());
        count = 0;
	}

    private static void Calculate(int n, int sum){
        for(int i = 0; i < 3; i++){
            if(n == 0 && i == 0){
                continue;
            }
            if(n == N){
                if(sum % 3 == 0) count++;
                return;
            } else {
                Calculate(n + 1, sum + i);
            }
        }
    }
}

• 생각

1. 이 문제를 풀 때 가장 중요하게 알아야 하는 것은 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾는 것이다. 어떻게 구할까??

합이 S인 K개의 양의 정수를 찾는 방법은 S를 K로 나눈 몫 K-1개와 나눈 몫+1 한개의 수인 K개의 수의 곱이 최대의 값을 가진다는 것이다.

• 코드

정답 코드 : 합이 S인 K개의 양의 정수를 찾는 방법은 S를 K로 나눈 몫 K-1개와 나눈 몫+1 한개의 수인 K개의 수의 곱이 최대의 값이다.

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

public class Main {
	static int S, K;

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

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

		S = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
	}

	private static long FindMaxValue() {
		int q = S / K; // 몫
		int r = S % K; // 나머지
		long max = 1;

		for (int i = 1; i <= K; i++) {
			if (i <= r) {// 나머지 갯수만큼 +1
				max *= (q + 1);
			} else {
				max *= q;
			}
		}

		return max;
	}
}

• 생각

1. 점화식은 어떻게 생각해야될 지 감이 오지 않는다..

• 코드

정답 코드 : 링크를 보고 이해하여서 코드를 작성했다. 다시 풀어봐야할 것 같음.

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

public class Algorithm {
	static int N, S;
	static int[] coin, dp;

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

	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());
		S = Integer.parseInt(st.nextToken());

		coin = new int[101]; 
		dp = new int[10001];

		for (int i = 1; i <= N; i++)
			coin[i] = Integer.parseInt(br.readLine());

		dp[0] = 1; 
	}

	private static void dp() {
		for (int i = 1; i <= N; i++) {
			for (int j = coin[i]; j <= S; j++) {
				dp[j] += dp[j - coin[i]];
			}
		}

	}
}

• 생각

1. 배열 1개(윷놀이 판)로해서 만들어서 주사위 수에 따라서 굴리며 백트래킹하면 될 것 같다. ==>> 윷놀이를 하다가 10, 20, 30 (들어가는 부분) 때 잘 구해지지 않았다.

2. 배열을 2차원으로 만든다. (들어가는 곳별로 판을 새롭게 만듬) 배열의 값은 주사위 값 별로 해당되는 점수를 넣어줌. 이 배열을 주사위 수에따라 굴리며 백트래킹

• 코드

정답 코드 : 맵을 4개를 만들어서 주사위 수에따라서 굴리며 백트래킹한다. 

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

public class Main {
	static int maxValue;
	static int[] dice, X, Y;
	static int[][] map;
	static boolean[][] check;

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

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

		dice = new int[10];
		map = new int[4][30]; // 각 판의 점수를 저장
		check = new boolean[4][30]; // 해당 지역에 말이 있는지 없는지 check
		X = new int[4]; // 각각 주사위 위치 말 번호 저장
		Y = new int[4]; // 각각 주사위 맵 위치 저장
		maxValue = Integer.MIN_VALUE;

		for (int i = 0; i < 10; i++)
			dice[i] = Integer.parseInt(st.nextToken());

		map[0] = new int[] { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, -1, -1, -1,
				-1, -1, -1, -1 };
		map[1] = new int[] { 0, 0, 0, 0, 0, 10, 13, 16, 19, 25, 30, 35, 40, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
				-1, -1, -1, -1 };
		map[2] = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 22, 24, 25, 30, 35, 40, -1, -1, -1, -1, -1, -1, -1, -1,
				-1, -1, -1 };
		map[3] = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30, 28, 27, 26, 25, 30, 35, 40, -1, -1, -1,
				-1, -1 };
	}

	private static void dfs(int index, int sum) {
		if (index == 10) {
			maxValue = Math.max(maxValue, sum);
			return;
		}
		for (int i = 0; i < 4; i++) {
			int tempX = X[i];
			int tempY = Y[i];

			if (map[X[i]][Y[i]] == -1)
				continue;
			check[X[i]][Y[i]] = false;

			//
			if (X[i] == 0) {
				switch (Y[i]) {
				case 5:
					X[i] += 1;
					break;
				case 10:
					X[i] += 2;
					break;
				case 15:
					X[i] += 3;
					break;
				}
			}

			Y[i] += dice[index];

			if (X[i] != 0) {
				// 바뀐 map의 주사위 위치에 따라 map을 바꿈
				switch (map[X[i]][Y[i]]) {
				case 40:
					X[i] = 0;
					Y[i] = 20;
					break;
				case 25:
					X[i] = 1;
					Y[i] = 9;
					break;
				case 30:
					X[i] = 1;
					Y[i] = 10;
					break;
				case 35:
					X[i] = 1;
					Y[i] = 11;
					break;
				}
			}

			if (!check[X[i]][Y[i]]) {
				if (map[X[i]][Y[i]] != -1) {
					check[X[i]][Y[i]] = true;
					dfs(index + 1, sum + map[X[i]][Y[i]]);
					check[X[i]][Y[i]] = false;
				} else {
					dfs(index + 1, sum);
				}
			}
			X[i] = tempX;
			Y[i] = tempY;
			check[X[i]][Y[i]] = true;
		}
	}
}

• 생각

1. 어디서 많이 본 문제같다. 백준 1781번 : 컵라면 문제이다. 

• 코드

정답 코드 : 배열에 값을 넣은 뒤 마감일로 오른차순 정렬을 한다. 그 후 우선순위 큐를 이용하여 풀었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
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(FindMaxValue());
	}
	
	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());
		}
		
		// 2차원 배열 정렬 (deadline 오름차순)
		Arrays.sort(array, new Comparator<int[]>() {
		    @Override
		    public int compare(int[] o1, int[] o2) {
		        return o1[0] - o2[0];
		    }
		});
	}
	
	private static int FindMaxValue() {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int sum = 0;
        for (int i = 0; i < N; i++) {
            queue.add(array[i][1]);
            while (!queue.isEmpty() && queue.size() > array[i][0]) queue.poll();
        }
        while (!queue.isEmpty())
            sum += queue.poll();
		return sum;
	}
}

• 생각

1. 어떻게 풀어야할 지 1시간 생각해봤지만 감이 오지 않았다.... 이중 for문으로 구해봤지만 역시나 시간 초과.. 결국 검색을 했다...!

• 코드

정답 코드 : 시작부터 끝까지의 부분합을 구하기 위해 (x2, y2)까지의 부분합을 더하고 (x1 - 1,  y2)과 (x2 , y1 - 1)을 빼줍니다. 그런데 이 때, 두 값을 뺀 부분의 교집합이 있으므로 해당 부분은 다시 더 해주는 방식을 사용했다.

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

public class Algorithm {
	static int[][] array;
	static int[][] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		array = new int[N + 1][N + 1];
		dp = new int[N + 1][N + 1];

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

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			sb.append(sum(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 
					Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())) + "\n");
		}
		
		System.out.println(sb);
	}

	static int sum(int x1, int y1, int x2, int y2) {
		return dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
	}
}