문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

 

 

https://www.acmicpc.net/problem/18858

 

18858번: 훈련소로 가는 날

1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,353으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

1. 이해 (5분) - 3분

문제 자체는 길지 않았지만, 이해하는데는 시간이 필요했습니다.

non-산 이라는 처음 보는 단어가 있어 머릿속으로 그려보는데 조금 어려움이 있었습니다.

몇 번을 다시 읽고 문제에서 주어진 '산'이라는 개념이 잡혀 풀이를 구상했습니다.


2. 계획 (5분) - 1분

풀이방법은 간단했습니다. non-산 이 되려면, 즉 산이 없으려면 문제에서 설명하듯 A1<A2>A3 형태의 부분수열이 없어야합니다. 이 말은 즉 A1 -> A2로 갈때 가능한 3가지 경우 (A2가 A1보다 크거나, 같거나 작거나)를 두번 거치며 생기는 9가지 경우의 수 중에서 하나의 경우가 막힌다는 뜻입니다.

가능한 방법의 갯수를 구해야하므로 DP형태로 이전 단계에서 가능한 방법의 수를 가지고 다음 단계를 구합니다.

이때 초기 데이터는 이전 턴에서 변화가 없었다를 1씩 넣어주고 이 후 상승이 가능한 경우, 하강이 가능한 경우를 계산해서 다음 데이터에 넣어주는 식으로 구현했습니다.


3. 검증 (5분) - 1분

제가 구상한 풀이방법에서는 가능한 이전 상태의 수 M개의 데이터를 기억하고 이를 토대로 N번 가능한 경우의 수를 계산합니다. 따라서 연산은 대력 MN번 일어날 것이고, 문제에서 입력의 범위가 100과 1000으로 주어졌기때문에 10만번이면 충분히 시간안에 정답이 나올것이라고 생각했습니다.

메모리적인 측면에서도 딱히 문제가 생길 부분이 보이지 않았습니다.


4. 풀이 (30분) - 19분

구상한 풀이방법을 토대로 코드를 작성했습니다.

 


5. 채점, 디버깅 (+30여분)

풀이자체는 시간이 많이 걸리지 않았지만... 

구현 과정에서 반대방향으로 돌아가는 반복문과 입력 데이터가 1,2인 경우 등의 예외처리 그리고 초기 구상에서 잘못생각한 부분등을 고치면서 디버깅에 시간이 꽤나 걸렸습니다.

다행히 예제로 주어진 데이터에서 오류를 발견할 수 있어서 수정해 제출했지만 예제 데이터로 알 수 없는 오류였다면 오답인지도 모른채로 제출할 뻔 했습니다...

 

추가로 디버깅을 통해 코드를 수정하다보니 + 초기에 풀이 형태를 대충 구상

이 두가지 허술함의 콤보로 코드가 상당히 난해하고 더러워졌습니다.

추후 수정하게되면 재업로드하겠습니다!

 

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

public class Main {
	static StringTokenizer st;
	static final long div = 998_244_353;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		long[][] before = new long[M + 1][3];
		long[][] now = new long[M + 1][3];

		for (int m = 1; m <= M; m++) {
			before[m][1] = 1;
		}

		long sum = 0;

		for (int n = 1; n < N; n++) {
			
			sum = 0;
			for (int m = M; m > 0; m--) {
				sum = (sum + before[m][0] + before[m][1]) % div;
				now[m-1][0] = sum;
			}
			
			sum = 0;
			now[1][1] = (before[1][0] + before[1][1] + before[1][2]) % div;
			sum = (sum + now[1][1]) % div;
			for (int m = 2; m <= M; m++) {
				now[m][2] = sum;
				now[m][1] = (before[m][0] + before[m][1] + before[m][2]) % div;
				sum = (sum + now[m][1]) % div;
			}
			
			before = now.clone();
			now = new long[M+1][3];
		}

		long answer = 0;

		for (int m = 1; m <= M; m++) {
			answer = (answer + before[m][0] + before[m][1] + before[m][2]) % div;
		}

		System.out.println(answer);
	}
}

 

 

 

 

728x90

루틴에 맞춰 풀어본 첫 문제입니다.

몸풀기를 할 생각으로 실버 문제를 골랐는데... 너무 빨리 끝나서 생각처럼 잘 되진 않았습니다 ㅋㅋ

문제풀이 루틴에 관한 글은

https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

 

https://www.acmicpc.net/problem/12849

 

12849번: 본대 산책

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.

www.acmicpc.net

 

숭실대학교 교내 대회에서 사용된 문제입니다.

설명도 직관적이고 DP의 개념을 잡기 좋은 문제인 것 같습니다. 

제가 짜 놓은 루틴대로 문제를 풀어보도록 하겠습니다.

 

1. 이해 (5분) - 1분

설명이 워낙 간단명료한 터라 이해에는 긴 시간이 걸리지 않았습니다. 

캠퍼스를 산책하고 주어진 시간에 시작점인 정보과학관에 도착하는 경로가 몇 개인지 알아내면 됩니다.

 

2. 계획 (5분) - 1분

우선 문제의 캠퍼스는 생긴 것 부터 그래프와 유사합니다. 시간이 정해져 있고 경로의 개수를 찾는 것이니 BFS를 생각해 볼만도 하지만 10만 분이라는 시간 후에 무시무시하게 많은 경로를 고려하면 안 될 것 같습니다.

대신 우리는 경로의 갯수만을 구하면 되고, 경로를 알 필요는 없다는 점에 착안해서 DP를 사용해 간단하게 구현이 가능할 것 같습니다. 

비슷한 느낌의 DP 문제로는 https://www.acmicpc.net/problem/2579  [계단오르기 (실버 3)]가 있을 것 같네요.

DP가 진행되는 기준이 시간과 계단으로 다르고 이 문제 같은 경우는 순환이 가능하단 차이가 있지만... 느낌이 비슷하다고 봐주시면 될 것 같습니다. 

특정 시간에 8개의 건물에 위치하는 경로의 갯수를 각각 저장하도록 [입력받은 시간][8]의 2차원 배열을 선언해 앞 시간의 정보를 토대로 풀이해보겠습니다.

그림처럼 건물들에 번호를 매기고

처음 시간 D=0일때 가능한 경로는 0번 건물이 1

D=1일 때 가능한 경로는 1,2번 건물이 각각 1

... 이런식으로 진행해나가려고 합니다.

3. 검증 (5분) - 1분

시간의 최대치는 10만, 제 계획에선 시간 1 당 8번의 덧셈 연산만 진행되면 되니 주어진 시간 1 초안에 무난하게 통과할 것 같습니다. (시간제한 1초를 대략 1억 번의 연산으로 생각하면 됩니다.)

문제에선 정답을 10억7로 나눈 나머지를 출력하라고 했는데, 풀이 도중에 int의 크기를 넘어서는 오버플로우가 발생하기 때문입니다.

매 연산마다 나누기를 진행해주면 되지만, 제가 구상한 풀이에선 신양관, 한경직기념관이 각각 4개의 값이 더해집니다.

그럼 최대 40억의 값이 나오므로 오버플로우를 방지하기 위해 아예 long 타입으로 배열을 선언해줍시다.

 

주어지는 입력으로 가능한 최대 80만개의 long타입 배열이 있다면 long타입의 크기는 16Byte로 사용하는 메모리는 1280만 Byte입니다.

1MB가 약 100만 Byte이므로 12MB가량의 메모리가 필요하고, JVM을 감안해도 문제에서 주어진 512MB의 메모리 안에서 충분히 동작할 것 같습니다.

 

 

4. 풀이 (30분) - 8분

여기까지 구상한 내용으로 풀어봅니다!

 

코드를 작성 한 뒤 주어진 예제를 넣어 확인합니다.

입력의 최솟값인 1과 10만을 넣어 출력이 정상적으로 되는 것을 확인합니다.

(움직이지 않고 머무르는 것이 불가능하므로 입력이 1인 경우 0이 나오는 것이 당연합니다. 10만을 입력한 경우의 정답은 지금 상황에서 확신할 수 없으므로 에러가 발생하지 않는지만 확인했습니다. )

 

5. 채점, 디버깅 (+@)

다행히 한번에 정답으로 통과되었습니다. 

이 문제를 푸는데는 총 11분이 걸렸습니다. 

실버 1의 난이도면 코딩 테스트에서 1,2번의 앞 순위로 나오는 문제니 스타트로 나쁘지 않았습니다!

DP를 구상하고 정답이 자료형의 크기를 넘치는것만 주의하면 크게 어려울 것이 없는 문제였습니다.

 

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

public class Main {
	static final long div = 1_000_000_007;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int D = Integer.parseInt(br.readLine());
		long[][] map = new long[D + 1][8];
		map[0][0] = 1;

		for (int d = 0; d < D; d++) {
			map[d + 1][0] = (map[d][1] + map[d][2]) % div;
			map[d + 1][1] = (map[d][0] + map[d][2] + map[d][3]) % div;
			map[d + 1][2] = (map[d][0] + map[d][1] + map[d][3] + map[d][5]) % div;
			map[d + 1][3] = (map[d][1] + map[d][2] + map[d][4] + map[d][5]) % div;
			map[d + 1][4] = (map[d][3] + map[d][5] + map[d][6]) % div;
			map[d + 1][5] = (map[d][2] + map[d][3] + map[d][4] + map[d][7]) % div;
			map[d + 1][6] = (map[d][4] + map[d][7]) % div;
			map[d + 1][7] = (map[d][5] + map[d][6]) % div;
		}

		System.out.println(map[D][0]);
	}
}

 

감사합니다!

728x90

https://www.acmicpc.net/problem/1202

 

1202번: 보석 도둑

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci

www.acmicpc.net

 

 

보석도둑 문제입니다.

핵심 아이디어는, 가방에 담을 수 있는 가장 비싼 보석을 담자! (Greedy)입니다.

다만 고려해야할 상황이 몇 개 있습니다.

 

우선 큰 가방에 비싼 보석을 담는다면 작은 가방에 아무것도 담지 못하는 비효율적인 상황이 생길 수 있습니다.

그러니 작은 가방을 먼저 채우는것이 좋습니다.

 

둘째, 가방의 갯수가 30만개, 보석의 가격이 100만까지 가능하므로 최대 3000억의 값이 정답으로 나올 수 있습니다.

정답을 long (C계열의 경우 longlong) 타입으로 선언해 주어야 오버플로우가 발생하지 않을 것 같습니다.

 

셋째, 보석과 가방의 갯수를 자세히 보시면... 둘 사이에는 부등호가 없습니다.

즉 가방이 보석보다 많을 수도 있다는 뜻입니다.

저는 이 부분을 놓쳐서 NullPoint Exception을 한 번 보았네요.

 

 

풀이로 들어가겠습니다.

작은 가방부터 넣을 수 있는 최대의 보석을 담습니다. 

저는 그래서 보석과 가방의 정보를 모두 받고, 둘을 모두 오름차순으로 정렬해 주었습니다.

 

그리고 정렬된 가장 가벼운 가방부터 담을 수 있는 가장 비싼 보석을 찾는데,

보석의 정보가 이미 정렬되어 있으므로 한 번 순회하며 자기가 담을 수 있는 보석까지만 PriorityQueue에 넣었습니다.

PriorityQueue의 Comparator를 람다식으로 설정해서 가치가 높은 보석이 위로 올라오게 했으므로 이 PriorityQueue안에는 내가 담을 수 있고 가장 비싼 보석이 위에 존재하게 됩니다.

PriorityQueue에서 보석 하나를 꺼내어 담는 처리를 하고 (정답에 누적합하고) 다음 크기의 가방에 대해 같은 작업을 반복하면 됩니다. 

 

좀 더 최적화된 방법이 있을것 같은데 나중에 생각나면 포스팅을 업데이트 하도록 하겠습니다!

 

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

public class Main{
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		PriorityQueue<int[]> pqueue = new PriorityQueue<int[]>((e1, e2) -> {
			return e2[1] - e1[1];
		});
		int[][] jewels = new int[N][2];
		int[] bags = new int[K];

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

		for (int k = 0; k < K; k++) {
			bags[k] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(jewels, (e1, e2) -> {
			return e1[0] - e2[0];
		});
		Arrays.sort(bags);

		int index = 0;
		long answer = 0;

		for (int k = 0; k < K; k++) {
			int nowBag = bags[k];

			while (index < N) {
				if (jewels[index][0] <= nowBag) {
					pqueue.add(jewels[index].clone());
					index++;
				} else {
					break;
				}
			}
			if(!pqueue.isEmpty()) {
				answer += pqueue.poll()[1];
			}
		}

		System.out.println(answer);
	}
}

 

 

 

 

728x90

https://www.acmicpc.net/problem/20040

 

20040번: 사이클 게임

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한

www.acmicpc.net

 

또 다른 웰 노운(Well Known인데 우리는 모르는) 알고리즘, 분리집합의 등장입니다. 

유니온이라고도 알려져 있습니다.

유니온은 일종의 단방향 트리라고 생각하셔도 될 것 같습니다.

데이터들을 집합들로 구분할때 어떻게 할 수 있을까요?

일일히 넘버링을 붙이거나 이름을 붙여도 되겠지만, 구현은 어떻게 하실건가요?

두개의 집합이 합쳐질때는요?

 

분리집합은 자신들을 대표하는 데이터를 부모로 가리킴으로서 자신이 속한 집합을 구분합니다.

 

이 데이터를 노드라고 생각한다면, 집합은 여러 노드들이 연결된 그래프가 되겠죠.

자신이 이미 속한 집합의 노드와 연결된다면 그 그래프는 사이클이 생긴 그래프가 됩니다.

간단하죠?

 

 

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

public class Main {
	static StringTokenizer st;
	static int[] parent;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int answer = 0;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		parent = new int[N];
		for (int n = 0; n < N; n++) {
			parent[n] = n;
		}

		for (int m = 1; m <= M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int aParent = findParent(a);
			int bParent = findParent(b);

			if (aParent == bParent) {
				answer = m;
				break;
			} else {
				parent[aParent] = bParent;
			}
		}

		System.out.println(answer);
	}

	static int findParent(int a) {
		if (parent[a] == a) {
			return a;
		} else {
			parent[a] = findParent(parent[a]);
			return parent[a];
		}
	}
}
728x90

https://www.acmicpc.net/problem/1806

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

 

또 다른 투 포인터 문제입니다. 

정확히는 슬라이딩 윈도라고 할 수 있겠네요. 

기본적인 투 포인터가 데이터의 양 쪽 끝에서 좁혀 들어오면서 탐색한다면, 슬라이딩 윈도는 한쪽 끝에서 시작해서 연속된 특정 범위를 찾습니다.

조금 더 상세히 설명해 볼까요?

 

N길이의 수열에서 연속된 부분을 구한다는 것은, 연속된 부분합의 시작점과 끝점을 정한다는 뜻입니다.

즉 N*N개의 경우가 존재한다는 뜻입니다.

슬라이딩 윈도우는 이 시작점과 끝점을 모든 경우에 대해 계산해보지 않고, 현재 부분에서 조건보다 작으면 연속된 부분을 늘리고 크면 연속된 부분을 줄이면서 진행합니다.

 

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

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		int[] num = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int n = 0; n < N; n++) {
			num[n] = Integer.parseInt(st.nextToken());
		}

		int left = 0;
		int right = 1;
		int sum = num[0];
		int answer = 100_001;

		while (left < N) {
			if (sum >= S) {
				answer = Math.min(answer, right - left);
				sum -= num[left];
				left++;
			} else {
				if (right == N) {
					break;
				} else {
					sum += num[right];
					right++;
				}
			}
		}
		if(answer == 100_001) {
			System.out.println(0);
		}else {
			System.out.println(answer);
		}
	}
}
728x90

https://www.acmicpc.net/problem/2467

 

2467번: 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -

www.acmicpc.net

 

정석적인 투포인터 문제입니다.

투포인터 알고리즘에 대해선 나중에 포스팅을 작성해 보도록 하겠습니다.

 

 

투포인터 알고리즘을 통해 절댓값이 0에 가장 가까운 두개의 특성값을 기록하고 출력하면 간단히 풀립니다.

 

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

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		int value = Integer.MAX_VALUE;
		int[] answer = new int[2];

		st = new StringTokenizer(br.readLine());

		for (int n = 0; n < N; n++) {
			num[n] = Integer.parseInt(st.nextToken());
		}

		int left = 0;
		int right = N - 1;

		while (left < right) {
			int sum = num[left] + num[right];
			int abs = Math.abs(sum);

			if (abs < value) {
				value = abs;
				answer[0] = num[left];
				answer[1] = num[right];
			}

			if (sum <= 0) {
				left++;
			} else {
				right--;
			}

		}
		System.out.println(answer[0] + " " + answer[1]);
	}
}
728x90

https://www.acmicpc.net/problem/2166

 

2166번: 다각형의 면적

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

www.acmicpc.net

 

신발끈 공식을 이용한 문제입니다.

고등학교때 배웠는지, 대학와서 선형대수학에서 배웠는지 모르겠지만...

워낙 간단하고 유용한 공식이라 아직 머릿속에 남아있어서 쉽게 해결했습니다.

 

공식에 대해 잘 모르시는 분은 아래의 킹무위키를 참고해 보셔도 될 것 같습니다! 흐흐...

https://namu.wiki/w/%EC%8B%A0%EB%B0%9C%EB%81%88%20%EA%B3%B5%EC%8B%9D

 

 

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

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		long[][] points = new long[N + 1][2];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			points[n][0] = Long.parseLong(st.nextToken());
			points[n][1] = Long.parseLong(st.nextToken());
		}
		points[N] = points[0].clone();

		long sum1 = 0L;
		long sum2 = 0L;

		for (int n = 0; n < N; n++) {
			sum1 += points[n][0] * points[n + 1][1];
			sum2 += points[n][1] * points[n + 1][0];
		}

		System.out.println(String.format("%.1f", Math.abs(sum1 - sum2) / 2D));
	}
}

 

 

입력의 범위가 10만이고, 둘을 곱하면 int의 크기를 넘어가는 것만 주의하시면 쉽게 풀 수 있습니다!

저는 눈치 못채서 걸렸습니다!! 으아아악!!

 

728x90

https://www.acmicpc.net/problem/14939

 

14939번: 불 끄기

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄

www.acmicpc.net

 

처음 문제를 보고, 뭐지 하는 생각이 들었습니다.

문제의 지문 자체는 간결하고 이해도 되는데 이 문제를 어떻게 구현할지 엄두가 안 나더라고요.

그나마 추측할 수 있는 부분은 입력의 크기가 고정되어있고 10x10 사이즈로 작다 보니 완전탐색으로 될 것 같다 정도였습니다. 고민을 좀 해봤지만 명쾌한 아이디어가 안 떠올라, 검색을 통해 접근 법을 찾았고 구현 자체는 어렵지 않았습니다.

 

핵심아이디어는 이것입니다.

한 줄씩 불꺼진 상태를 고정시키자.

불 켜진 줄을 누르게 되면, 좌 우의 전구가 동시에 on off되기 때문에 확실하게 불이 꺼진 줄을 만드는 방법은 해당 줄의 위나 아래의 전구를 누르는 것 뿐입니다.

이 방법을 9개의 줄에 적용합니다.

이제 1~9번줄의 전구는 모두 꺼졌다는 명제는 자명합니다. 따라서 10번째 줄의 전구만이 켜져있을 가능성이 있습니다.

10번째 줄의 전구가 모두 꺼졌다면 모든 전구가 꺼져있는 상태입니다.

 

여기서 우리는 의문을 갖습니다.

위에서 생각한 방식을 그리디하게 적용하면 놓치는 케이스가 생기지 않을까?

네! 놓치는 경우가 생깁니다!

첫 번째 줄의 현재 상태에서만 그리디하게 진행하면 불을 다 끌수 있는데도 놓치는 경우가 생깁니다. 그렇다고 모든 전구에 대해 가능한 경우를 계산하면 2^100가지의 경우가.. 각 케이스마다 적용해야 하는 추가연산이 있는데 10억개의 경우는 너무 가혹합니다.

하지만, 위의 방식을 잘 생각해보면 첫 줄의 전구 상태에 따라 다음 작업들은 종속적으로 일어남을 알 수 있습니다.

따라서 우리가 찾아봐야 할 경우의 수는 첫번째 줄에서 일어날 수 있는 모든 경우인 2^10가지, 1024가지에 불과한것입니다.

 

1024가지 경우를 모두 돌려보는데엔 여러 방법이 있을텐데,

저는 개인적으로 비트마스킹 기법에 꽤나 익숙한 터라 해당 방법을 통해 구현했습니다.

 

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

public class Main {
	static int answer = Integer.MAX_VALUE;
	static int[][] delta = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static boolean[][] testmap = new boolean[10][10];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		boolean[][] map = new boolean[10][10];

		for (int n = 0; n < 10; n++) {
			char[] line = br.readLine().toCharArray();
			for (int m = 0; m < 10; m++) {
				if (line[m] == 'O') {
					map[n][m] = true;
				}
			}
		}

		for (int i = 0; i < 1024; i++) {
			copy(map);
			int count = 0;

			for (int j = 0; j < 10; j++) {
				if (((1 << j) & i) != 0) {
					on(0, j);
					count++;
				}
			}

			for (int n = 0; n < 9; n++) {
				for (int m = 0; m < 10; m++) {
					if (testmap[n][m]) {
						on(n + 1, m);
						count++;
					}
				}
			}

			if (checkLight()) {
				answer = Math.min(answer, count);
			}
		}

		if (answer < Integer.MAX_VALUE) {
			System.out.println(answer);
		} else {
			System.out.println(-1);
		}
	}

	static boolean checkLight() {
		for (int i = 0; i < 10; i++) {
			if (testmap[9][i]) {
				return false;
			}
		}
		return true;
	}

	static void copy(boolean[][] map) {
		for (int i = 0; i < 10; i++) {
			testmap[i] = map[i].clone();
		}
	}

	static void on(int x, int y) {
		for (int i = 0; i < 5; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY)) {
				testmap[nX][nY] = !testmap[nX][nY];
			}
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x <= 9 && 0 <= y && y <= 9) {
			return true;
		}
		return false;
	}
}

 

감사합니다!!

728x90

+ Recent posts