선장 일지

• 생각

가로,세로로 인접한 7명의 학생중 이다솜파가 4명이상 있을 수 있는 수를 출력하면 되는 문제이다.

dfs를 통해 basecase를 7명학생으로하고 7명 학생 중 4명이상이 이다솜파이면 count를 증가시키는 식으로 하면될 것 같다. (배열을 돌 때 인접한 7명을 상하좌우로 반복문을 돌리면서 찾으니 모든 7명의 경우의 수를 찾지 않게된다.)

• 코드

정답 코드 : 백트래킹을 이용해 풀었다. 배열을 돌리는 과정을 나중에 한번 더 공부하면 좋을 듯

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 answer;
	static char[][] array;
	static boolean[] check;
	static int[] x = { -1, 0, 1, 0 };
	static int[] y = { 0, -1, 0, 1 };

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

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

		answer = 0;
		array = new char[5][5];
		check = new boolean[1 << 25];
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < 5; i++) {
			String s = br.readLine();
			for (int j = 0; j < 5; j++) {
				array[i][j] = s.charAt(j);
				if (array[i][j] == 'S')
					queue.offer(new int[] { i, j });
			}
		}

		while (!queue.isEmpty()) {
			int location[] = queue.poll();
			check[1 << (location[0] * 5 + location[1])] = true;
			dfs(1, 1, 1 << (location[0] * 5 + location[1]));
		}
	}

	private static void dfs(int count, int lee, int mark) {
		// basecase
		if (count == 7) {
			if (lee >= 4) {
				answer++;
			}
			return;
		}
		for (int i = 0; i < 25; i++) {
			if ((mark & (1 << i)) == 0)
				continue; // 현재 경로찾기

			for (int k = 0; k < 4; k++) {
				int r = i / 5 + x[k];
				int c = i % 5 + y[k];

				if (r < 0 || r >= 5 || c < 0 || c >= 5)		continue;
				
				int number = r * 5 + c;
				if (check[mark | (1 << number)]) 	continue; // 이미 방문했다면

				check[mark | (1 << number)] = true;
				if (array[r][c] == 'S')
					dfs(count + 1, lee + 1, mark | (1 << (number)));
				if (array[r][c] == 'Y')
					dfs(count + 1, lee, mark | (1 << (number)));
			}
		}
	}
}

반복문 돌리는 방법을 배운 곳

suriisurii.tistory.com/37

• 생각

어떻게 풀어야되는 지 느낌이 오지않아서 다른 사람이 잘 설명해 준 곳에서 이해하였다.

pangtrue.tistory.com/m/265

감이 오지 않으면 설명 보는 것이 좋을 것 같다.

• 코드

정답 코드 : dfs를 통해 구현하였다. 그래프 형식으로 푸는 문제들이 익숙하지 않아서 나중에 한번 더 풀어보면 좋을 것 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, answer;
	static int[] array;
	static boolean[] check, reCheck;
	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;

		sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int i = 1; i <= T; i++) {
			N = Integer.parseInt(br.readLine());
			answer = N;
			array = new int[N + 1];
			check = new boolean[N + 1];
			reCheck = new boolean[N + 1];
			
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++)
				array[j] = Integer.parseInt(st.nextToken());
			
			for (int j = 1; j <= N; j++) {
				if (check[j] == false) {
					check[j] = true;
					dfs(j);
				}

			}

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

	}

	private static void dfs(int number) {
		int next = array[number];
		if (check[next] == false) {
			check[next] = true;
			dfs(next);
		}
		if (reCheck[next] == false) {		// 한번 갈때마다 N에서 빼줌
			answer--;
			for (int i = next; i != number; i = array[i])
				answer--;
		}

		reCheck[number] = true;
	}
}

• 생각

해당 문제에서는 색칠되는 사각형의 왼쪽 아래 x,y좌표와 오른쪽 위 x,y좌표를 주지만

이걸 나는 이걸 왼쪽 위 x,y 좌표와 오른쪽 아래 x,y 좌표로 이용했다.

이렇게 이용하게 되면 문제에서 주는 예시의 그림과는 반대로 나오지만

구분되는 영역과 넓이는 동일하기 때문에 이렇게 풀이했다.

로직은 색칠되는 사각형 영역에 해당하는 배열에 1을 넣어서 

bfs 탐색을 하며 배열의 값이 0인 곳들을 상하좌우 탐색하면서 넓이를 구했다.

• 코드

정답 코드 : queue를 이용한 bfs로 구현하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, K;
	static int[][] array;
	static boolean[][] check;
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };
	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 = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		array = new int[N][M];
		check = new boolean[N][M];
		sb = new StringBuilder();
		ArrayList<Integer> list = new ArrayList<Integer>();

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int leftX = Integer.parseInt(st.nextToken()); // 왼쪽 위 x
			int leftY = Integer.parseInt(st.nextToken()); // 왼쪽 위 y
			int rightX = Integer.parseInt(st.nextToken()); // 오른쪽 아래 x
			int rightY = Integer.parseInt(st.nextToken()); // 오른쪽 아래 y
			for (int a = leftY; a < rightY; a++) {
				for (int b = leftX; b < rightX; b++) {
					array[a][b] = 1;
				}
			}
		}

		int count = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!check[i][j] && array[i][j] == 0) {
					int data = bfs(i, j);
					list.add(data);
					count++;
				}
			}
		}

		System.out.println(count);
		Collections.sort(list);
		for (int i = 0; i < list.size(); i++) {
			sb.append(list.get(i) + " ");
		}
	}

	private static int bfs(int a, int b) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] { a, b });
		check[a][b] = true;
		int count = 1;

		while (!queue.isEmpty()) {
			int[] location = queue.poll();

			for (int direction = 0; direction < 4; direction++) {
				int r = location[0] + x[direction];
				int c = location[1] + y[direction];

				if (r < 0 || c < 0 | r >= N || c >= M)	continue;

				if (!check[r][c] && array[r][c] == 0) {
					check[r][c] = true;
					queue.offer(new int[] { r, c });
					count++;
				}

			}
		}
		return count;
	}
}

• 생각

첫번째 고정된 VIP석을 제외한 나머지 가짓수에 대해서 곱으로 전체 경우를 구한다는 것

두번째는 Vip좌석을 통해서 남겨진 좌석을 지정된 방법으로 섞었을때 가능한 경우의 수 찾는 것

잘 이해되지 않으면 참고하면 좋을 것 같다.

http://blog.naver.com/occidere/220854811310

• 코드

정답 코드 : 점화식을 통해 구현한 코드이다.

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

public class Main {
	static int T, answer;
	static int[] dp;

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

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

		T = Integer.parseInt(br.readLine());
		answer = 1;
		dp = new int[41];
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= T; i++)
			dp[i] = dp[i - 1] + dp[i - 2];

		int n = Integer.parseInt(br.readLine());
		int start = 0;
		int stop = 0;
		for (int i = 0; i < n; i++) {
			stop = Integer.parseInt(br.readLine());
			answer *= dp[stop - start - 1];
			start = stop;
		}
		
		answer *= dp[T-stop];
		System.out.println(answer);
	}
}

• 생각

[JAVA] 백준 2293번 : 동전 1

위 문제랑 비슷하지만 다르다.

다른점은 동전 1에서는 S 원을 만들 수 있는 모든 경우의 수를 구하지만,

동전 2에서는 최소한의 동전을 사용해서 만들 때 사용한 동전의 개수를 구하는 문제이다.

잘 생각이 안나서 찾아보니 점화식음 다음과 같다.

dp[j] = Math.min(dp[j], dp[j-coin[i]]+1);

1. 사용한 동전의 개수가 최악일 경우 100,000개이기 때문에 10001로 초기화 한다.

2. 점화식의 구조를 따르기 위해 dp[0] = 0으로 초기화한다.

3. dp[S] = 100001이면 해당 금액을 만들 수 없다는 의미이므로 -1을 출력한다.

• 코드

정답 코드 : 점화식을 통해 구현했다.

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

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

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

	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]; // 인덱스 번호 1부터 +1씩 해서 배열 선언
		dp = new int[10001];

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

		Arrays.fill(dp, 10001);
		dp[0] = 0;
	}

	private static void dp() {
		// i는 x번째->coin[x번째 동전 종류]의 경우를 의미
		// j는 i의 동전 종류로 1~s원를 채우는 경우의 수를 의미
		for (int i = 1; i <= N; i++) {
			for (int j = coin[i]; j <= S; j++) {
				dp[j] = Math.min(dp[j], dp[j-coin[i]]+1);
			}
		}
		
		if(dp[S] == 10001)
			value = -1;
		else
			value = dp[S];
	}
}

• 생각

처음 풀어보니 시간초과가 떴다. 다른 사람이 잘 정리해놓은 것을 가져왔다. (링크)

문제에서 매우매우 중요한 키워드가 두 개 있다.

첫 번째로 'M이 하나 이상 존재하는 경우로만 주어진다' 이다.

두 번째로 '나머지가 모두 같게 되는 M을 찾으려고 한다' 이다.

이 두 문장을 잘 생각해보면 다음과 같다. '나머지가 같은 경우는 반드시 존재하며 이 때의 M은 모든 수에서 동일하다.'

그러면 모든 수에서 '동일하다'라는 의미는 결과적으로 M은 공약수라는 말 아니겠는가?

즉, 위 문제의 예제로 보면 이렇다는 것이다.

6 / M + r

34 / M + r

38 / M + r

여기서 r은 모두 같다는점. 즉, r만 0으로 만들 수 있다면 M을 쉽게 구할 수 있다는 것이다. 

(6 / M + r) - (34 / M + r) 을 풀어서 다시 묶어 표현하면

(6 - 34) / M 이라는 식이 나온다.

다음으로 (34 / M + r) - (38 / M + r) 을 풀어서 다시 묶어 표현하면

(34 - 38) / M 이라는 식이 나온다.

그리고 M은 모두 같다는 의미는 앞서 말했듯 (6 - 34) / M 라는 식과, (34 - 38) / M 의 M이 같다는 말이고,

다르게 표현하면 M은 (6 - 34)와 (34 - 38)의 공약수라는 의미라는 것.

만약 다른 예제로 17, 34, 24, 52, 39 가 있으면,

(17 - 34)와 (34 - 24)와 (24 - 52)와 (52 - 39)의 공약수를 찾으면 된다는 것이다.

그러면 이제 공약수를 찾을 일만 남았다. 공약수를 찾는 방법은 매우 쉽지 않은가?

최대공약수가 무엇인가? 최대공약수는 '공약수들 중에서 가장 큰 값' 아니던가. 즉, 거꾸로 최대공약수를 찾고 최대공약수와 그의 약수들을 구하면 끝이다.

• 코드

정답 코드 : 유클리드 호제법을 이용하여 구현했다.

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

public class Main {
	static int N, M;
	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));
		
		N = Integer.parseInt(br.readLine());
		sb = new StringBuilder();
		int[] array = new int[N];	
		
		for(int i = 0; i < N ; i++) 
			array[i] = Integer.parseInt(br.readLine());
		 
		Arrays.sort(array);		 
		int gcdValue = array[1] - array[0];	// 음수가 되지 않도록 큰 수에서 작은 수로 빼줌
	 
		for(int i = 2; i < N; i++) {
			// 직전의 최대 공약수와 다음 수(array[i] - array[i - 1])의 최대공약수를 갱신 
			gcdValue = getGCD(gcdValue, array[i] - array[i - 1]);
		}
	
		for(int i = 2; i <= gcdValue; i++) {
			// i가 최대공약수의 약수라면 출력
			if(gcdValue% i == 0) {
				sb.append(i + " ");
			}
		}
	}

	private static int getGCD(int p, int q) {
		if (q == 0) {
			return p;
		}
		return getGCD(q, p % q);
	}

}

• 생각

octorbirth.tistory.com/243여기를 통해 이해하였다.

2 * N 직사각형이 주어질 때, 2×1과 2×2 타일로 채우는 방법의 수

[구현]

Dynamic Programming (DP) 이용.

▶ DP[i] = 2 * i 직사각형에서 방법의 수

3 ≤ i 일 때, DP[i]는 DP[I-1]에서 크기  『1』만큼 늘어났기에 

□ 을 놓는 경우입니다.

① DP[i-1]에서 2*1 크기의 □을 놓는 경우입니다.

     ■ 영역은 작은 단계에서 부터 쌓여온것이기 때문에 어떤 형태든 신경쓰지 않습니다.

② DP[i-2]에서 2*2 크기의 □ 1개 or 2*1 크기의 □를 2개 놓는 경우입니다. 

    → DP[i-2] * 2 

▶ DP[i] = DP[i-1] + (DP[i-2] × 2)

※ 0 ≤ n ≤ 250이기 때문에 Java의 경우 BigInteger 이용.

※ 문제 조건상 i = 0일 때, DP[0] = 0도 정의

• 코드

정답 코드 : 점화식으로 구현하였다.

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

public class Main {
	static StringBuilder sb;
	static BigInteger[] dp;

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

	private static void SetData() throws Exception {
        Scanner sc = new Scanner(System.in);
		
		dp = new BigInteger[251];
		sb = new StringBuilder();
		
        dp[0] = new BigInteger("1"); 
        dp[1] = new BigInteger("1");
        dp[2] = new BigInteger("3");
        for(int i=3; i<=250; i++) {
            dp[i] = dp[i-2].multiply(new BigInteger("2"));
            dp[i] = dp[i].add(dp[i-1]);
        }
        
        while(sc.hasNextInt()){
            int n = Integer.parseInt(sc.next());
            sb.append(dp[n] + "\n");
         }
	}
}

• 생각

먼저 1번부터 N번째 입력했을때 최댓값의 메모를위한 dp[N+1]부터 만들어 놓자.

N번째의 입력은 1번째버튼을 입력하거나 4번째 버튼을 입력해야한다.

1번째 입력을 했다 가정하고 dp[i]=dp[i-1]로 초기화를 한다.

4번째 버튼을 입력할땐 몇번 연속 4번째 버튼을 입력하였는지가 중요하다.

왜냐하면 4번째 버튼을 처음 입력하기 2개전의 값이 버퍼에 복사되고 

dp[i]=dp[k]*(4번째버튼 입력횟수+1)이 되기 때문이다.

• 코드

정답 코드 : 점화식을 찾아 구현하였다.

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

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

	public static void main(String[] args) throws Exception {
		SetData();
		FindMaxValue();
		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 long[101];
	}

	public static void FindMaxValue() {
		for(int i = 1; i <= N; i++) {
			dp[i]=dp[i-1]+1;
			for(int j = 1; j <= i - 3; j++) {
				dp[i] = Math.max(dp[i], (j+1)*dp[i-(j+2)]);
			}
		}
	}

}