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

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

 

18248번: 제야의 종

첫 줄에 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 100)이 주어진다. i+1(1 ≤ i ≤ N)번째 줄에는 M개의 정수 ai,1, ai,2, ..., ai,M 이 주어지는데, ai,j가 1이면 사람 i가 j 번째 타종을 들었음을 의미하고, 0이면 듣

www.acmicpc.net

상당히 재밌는 문제였습니다. 

 

 

얼핏보면 이게 뭔소리지 싶은 문제일 수도 있습니다.

하지만 소리가 발생한 지점으로부터 원형으로 퍼져나간다는 사실을 생각해보면 쉽게 풀이방법을 알아 낼 수 있습니다.

주어진 예제가 너무 단편적이니 제가 직접 예제를 만들어 보겠습니다.

 

10 5
1 0 1 0 1
0 0 0 0 0
0 0 1 0 0
1 0 1 0 1
1 0 1 0 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 0 0

조건에 성립하는 예제라고 가정하고, 이 예제를 시각적으로 나타내 볼까요?

 

네, 그림을 보고 슬슬 느끼셨을것 같은데요.

이 문제는 정렬 문제입니다.

소리가 원형으로 퍼지기 때문에 바깥 사람이 들은 종소리를 더 가까운 사람은 무조건 들을 수 밖에 없죠.

따라서 종소리를 들은 숫자대로 사람들을 내림차순으로 정렬한다면,

안의 사람이 듣지 못한 종소리를 더 바깥에 있는 사람이 듣는 일은 없습니다.

(안의 사람이 들은 종소리를 바깥사람이 못듣는 경우는 당연히 존재합니다.)

 

예시를 살짝 바꿔 볼까요??

 

10 5
1 0 1 0 1
0 0 0 0 0
0 0 1 0 0
1 0 1 0 1
1 0 1 0 0
0 0 1 0 0
1 0 1 0 0
0 1 0 0 0
1 0 1 1 1
0 0 1 0 0

만약 바꾼 예시처럼 8번 사람이 아무도 듣지 못한 2번 종소리를 들었다고 가정해 봅시다.

그럼 8번은 다른 모두보다 종에 가까이 있어야 하는데, 그렇다면 다른 종소리도 자연스럽게 듣게 됩니다.

옳바른 예시와 잘못된 예시를 정렬 해보면 이렇게 되겠네요.

 

옳은 예

10 5

1 0 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 1 0 0
1 0 1 0 0
0 0 1 0 0

0 0 1 0 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 0

 

틀린 예

10 5

1 0 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 1 0 0
1 0 1 0 0
0 0 1 0 0

0 0 1 0 0

0 0 1 0 0

0 1 0 0 0

0 0 0 0 0

 

모순관계가 생기면 문제에서 주어진 예시 2번 처럼 어떻게든 0->1로 바뀌는 모습이 나타날 수 밖에 없습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 M = Integer.parseInt(st.nextToken());

		int[][] people = new int[N][M + 1];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			int sum = 0;
			for (int m = 0; m < M; m++) {
				people[n][m] = Integer.parseInt(st.nextToken());
				sum += people[n][m];

			}
			people[n][M] = sum;
		}

		Arrays.sort(people, (e1, e2) -> {
			return e2[M] - e1[M];
		});

		boolean answer = true;

		loop: for (int m = 0; m < M; m++) {
			int check = people[0][m];
			for (int n = 0; n < N; n++) {
				if(check < people[n][m]) {
					answer = false;
					break loop;
				}
				check = people[n][m];
			}
		}

		if (answer) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

 

728x90

가장 기본적인 자료구조이자, 앞으로 지겹도록 보게 될 JAVA의 배열에 관해 알아보겠습니다.

배열의 이론적인 부분은 다 아신다고 생각하고, 활용적인 면을 위주로 정리해보았습니다.

어느 정도 경험이 있으신 분들은 맨 아래의 코드만 보셔도 이해가 가능할 것 같습니다.

 

 

1. 선언

int[] array0;

선언만 하고 값의 대입은 나중으로 미룰 수 있다.


int[] array1 = new int [10];

배열의 크기만 잡아 선언하면 안의 값은 default값으로 채워진다.

 

int[] array2 = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };

최초에는 직접 값을 넣으면서 선언이 가능하다.

값을 변경할 때는 불가능하지만 새로운 배열을 만들어서 넣어주는 건 가능하다.

 

int[] array3 = new int [] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

새로운 배열을 만들면서 값을 곧바로 대입한다. 이 방법으론 나중에도 값의 변경이 가능하다.

ex) array3 = new int[] {1,2,3,4};

 

2. 기본 값

System.out.println(Arrays.toString(array1));

"{0,0,0,0,0,0,0,0,0,0}"

배열에 아무런 값을 넣지 않을 시 초기값은 0이다. (Int 타입의 경우, Boolean 타입은 false가 들어간다.)

 

3. Java.util.Arrays

Arrays를 import 하면 배열과 관련된 여러 유용한 메서드를 사용할 수 있다.

 

Arrays.fill();

배열 안을 지정된 값으로 채운다.

Arrays.toString();

기본적으로 toString()을 사용하거나 배열 자체를 출력하면 주소 값이 출력된다. Arrays.toString 메서드를 활용하면 배열의 값을 보기 좋게 출력한다. 

Arrays.sort();

배열의 원소들을 정렬한다. 기본적으론 오름차순 정렬이고, 정렬의 기준은 타입에 따라 내부적으로 구현된 compare메서드를 따른다.

 

람다식을 활용한 정렬

Arrays.sort(array, (e1, e2)->{
      return e1[1] - e2[1];
});

이런 식으로 람다식을 활용하면 내림차순 정렬은 물론이고 원하는 어떤 방식으로도 정렬이 가능하다.

단, 기본 타입 (Primitive) 배열엔 적용이 불가능하기 때문에, 동치 되는 class를 사용하면 된다.

ex) int[] -> Integer[] , char[] -> Character[] 등..

 

4. 주소 값 문제

JAVA는 기본 타입의 경우 Call by Value로 값을 전달하고 객체들의 경우엔 주소 값을 전달합니다.

배열도 객체로 취급되어 주소가 전달되다 보니, 개발자의 생각과 다르게 동작하는 경우가 생깁니다.

반복문을 통해 값을 하나하나 대입하는 방법도 있지만, clone메서드를 사용하면 쉽게 값의 복사가 가능합니다.

 

int[] array4 = array2;

array2의 주소 값이 들어갔다.

array4를 수정하면 array2도 동시에 수정되고, array2를 수정하면 array4도 바뀐다.


int[] array5 = array2.clone();

array2의 현재 상태를 복사해서 새로운 배열을 생성했다.

이후 둘의 수정은 서로에게 영향을 끼치지 않는다!

 

for(int i = 0; i < array.length; i++){

    copyArr[i] = arr[i].clone();

}

이런 식으로 반복문을 활용해 다차원 배열의 복사도 가능하다!

 

import java.util.Arrays;

public class Main {
	public static void main(String[] args) {

		int[] array0;
		int[] array1 = new int[10];
		int[] array2 = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		int[] array3 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		System.out.println("----> array의 기본 값은 0");
		System.out.println(Arrays.toString(array1));

		System.out.println("----> array2");
		System.out.println(Arrays.toString(array2));

		int[] array4 = array2;
		int[] array5 = array2.clone();

		Arrays.sort(array2);

		System.out.println("----> array2 sort 후");
		System.out.println(Arrays.toString(array2));
		System.out.println("----> array4는 array2의 주소를 가리킨다.");
		System.out.println(Arrays.toString(array4));
		System.out.println("----> array5는 array2의 값을 복사했다.");
		System.out.println(Arrays.toString(array5));

		System.out.println("----> array3");
		System.out.println(Arrays.toString(array3));

		array3 = new int[] { 1, 1, 1, 1 };

		System.out.println("----> array3에 새로운 값 넣기");
		System.out.println(Arrays.toString(array3));

		Arrays.fill(array3, 999);

		System.out.println("----> array3 값 채우기");
		System.out.println(Arrays.toString(array3));

		Integer[] array6 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		System.out.println("----> Integer 배열 array6");
		System.out.println(Arrays.toString(array6));
		Arrays.sort(array6, (e1, e2) -> {
			return e2 - 21;
		});
		System.out.println("----> array6 역순으로 sort");
		System.out.println(Arrays.toString(array6));

		System.out.println("인자로 전달해 출력하기");
		printArr(array1);

		System.out.println("인자로 전달해 변경하기");
		System.out.println(Arrays.toString(array1));
		fillArr(array1);
		System.out.println(Arrays.toString(array1));

		Integer[][] array7 = { { 1, 2, 3, 4 }, { 4, 3, 2, 1 }, { 4, 1, 2, 3 }, { 1, 4, 3, 2 } };

		System.out.println("----> array7 출력");
		System.out.println(Arrays.toString(array7));

		System.out.println("----> array7 반복문 출력");
		for (int i = 0; i < array7.length; i++) {
			System.out.println(Arrays.toString(array7[i]));
		}

		Integer[][] array8 = { { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, { 4, 3 }, { 3, 1, 5 }, { 1, 4, 3 } };
		System.out.println(array8.length);
		for (int i = 0; i < array8.length; i++) {
			System.out.println("----> array8의 길이 출력");
			System.out.println(array8[i].length);
		}

		Arrays.sort(array8, (e1, e2) -> {
			return e1[1] - e2[1];
		});

		System.out.println("----> array8 두번째 원소로 정렬해 출력");
		for (int i = 0; i < array8.length; i++) {
			System.out.println(Arrays.toString(array8[i]));
		}

		Arrays.sort(array8, (e1, e2) -> {
			return e1.length - e2.length;
		});

		System.out.println("----> array8 배열 길이로 정렬해 출력");
		for (int i = 0; i < array8.length; i++) {
			System.out.println(Arrays.toString(array8[i]));
		}

		int[] array9 = { 1, 2, 3, 4, 5 };
		int[] array10 = { 1, 2, 3, 4, 5 };

		System.out.println(array9.equals(array10));
	}

	static void printArr(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}

	static void fillArr(int[] arr) {
		Arrays.fill(arr, 1);
	}
}

 

728x90

'🔠 Language > ☕ Java' 카테고리의 다른 글

[JAVA] 함수 Interface  (0) 2021.12.07
[JAVA] PS에 유용하게 쓰이는 JAVA의 입출력 방법들  (0) 2021.11.26

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

 

4600번: 정글의 법칙

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 음수 -B와 양수 P가 주어진다. B는 다리의 수이고, P는 사람의 수이다. B와 P는 20을 넘지 않는다. (B가 음수로 주

www.acmicpc.net

(문제가 무척 길어서 스크린샷은 생략..)

 

대학교 후배가 실버도장깨기를 하다가 막혔다며 SOS를 친 문제다.

자신만만하게 OK사인을 보내고 문제를 풀러갔다가, 100명도 되지 않는 적은 정답자 수에 놀라고 어마어마하게 긴 문제의 길이에 놀라고 불친절한 Input에 놀라고... 아무튼 생각보다 난이도 있는 문제였다.

 

처음에는 각 나무를 일종의 PriorityQueue처럼 보고 가능한 경우의 수를 모두 계산해서 최적해를 구하는 식으로 짜려고 했는데, 예외와 조건이 너무 많아서 불가능했다.

다른 후배도 같이 도전하던 와중에 그 친구가 먼저 정답을 통과했고, 전체적인 시간을 가지고 관리한다는 tip과 놓치고 있던 조건(최적해를 위해 기다리는것이 금지된다. 건널 수 있으면 바로 건넌다.)을 듣고 바로 구현을 마칠 수 있었다.

 

나무에 대기하고 있는 사람과

다리를 건너고 있는 사람

 

두개의 데이터를 가지고 가장 시간이 적게 걸리는 그룹이 다리를 건너는 시점마다를 트리거로 동작시켜서

빈 다리에 건널 사람이 있다면 채워 넣고, 다리를 건너는 그룹들은 남은 시간을 줄이는 식으로 구현했다.

 

코드는 이렇다.

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

public class Main {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

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

		while (true) {
			st = new StringTokenizer(br.readLine());
			int B = Integer.parseInt(st.nextToken())*-1;
			int P = Integer.parseInt(st.nextToken());

			if (B == 0 && P == 0) {
				break;
			}
			int[] trees = new int[B + 1];
			trees[0] = P;
			trees[B] = -P;
			int[][] bridges = new int[B][2];
			int[][] groups = new int[B][2];
			int totalTime = 0;

			for (int b = 0; b < B; b++) {
				st = new StringTokenizer(br.readLine());
				bridges[b][0] = Integer.parseInt(st.nextToken());
				bridges[b][1] = Integer.parseInt(st.nextToken());
			}

			while (trees[B] < 0) {
				int time = Integer.MAX_VALUE;
				for (int b = 0; b < B; b++) {
					if (trees[b] > 0 && groups[b][0] == 0) {
						groups[b][0] = Math.min(trees[b], bridges[b][0]);
						groups[b][1] = bridges[b][1];
						trees[b] -= groups[b][0];
					}
					if (groups[b][1] > 0) {
						time = Math.min(groups[b][1], time);
					}
				}

				totalTime += time;

				for (int b = 0; b < B; b++) {
					if (groups[b][1] > 0) {
						groups[b][1] -= time;
						if (groups[b][1] == 0) {
							trees[b + 1] += groups[b][0];
							groups[b][0] = 0;
						}
					}
				}
			}
			sb.append(totalTime).append("\n");
		}

		System.out.println(sb);
	}
}

 

 

728x90

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

 

2565번: 전깃줄

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는

www.acmicpc.net

백준 사이트의 2565번 전깃줄이라는 문제입니다.

 

문제 설명은 간단하지만 막상 풀이 방법을 떠올리려면 떠오르지 않는 문제입니다.

솔직히 말하면 저도... 검색을 통해 다른 사람들의 풀이를 보고 풀었는데, 이 문제는 LIS(Longest Increase Subsequence)의 응용문제로 DP와 이분 탐색 두 가지의 방법으로 풀이가 가능합니다. 

DP의 경우 구현과 이해가 쉽지만 입력의 갯수가 많으면 시간 초과로 문제를 틀릴 가능성이 있다는데,

 

마침 문제가 입력의 갯수가 100개인 전깃줄 1과 10만 개인 전깃줄 2로 나뉘어 있으니 두 가지 방법을 각각 활용해서 풀어보도록 하겠습니다. 먼저 DP를 활용한 풀이 방법을 보겠습니다.

개념은 간단합니다, 전깃줄이 같은 곳에 걸쳐있지 않는다는 조건을 활용하여 입력을 정렬하고, 사용할 전깃줄의 갯수를 하나씩 늘려가며 전깃줄의 부분집합이 만들 수 있는 최댓값을 기록합니다. 이때 구한 최댓값을 DP 배열에 저장하고, 다음 풀이에서 활용할 수 있습니다.

 

예제 입력을 통해 확인해 보겠습니다.

(1,8), (3,9), (2,2) ,(4,1), (6,4), (10,10), (9,7), (7,6) 이렇게 8개의 전깃줄이 들어왔습니다.

이를 전깃줄의 시작 위치를 기준으로 정렬하면

(1,8), (2,2) ,(3,9), (4,1), (6,4), (7,6), (9,7), (10,10)와 같은 형태가 됩니다. 진행 방향은 상관이 없지만, 저는 뒤에서부터 쌓아가며 진행하도록 하겠습니다.

 

(10,10) 하나를 추가하고 -> 이때의 LIS길이는 당연히 1이 됩니다.

(9,7)를 추가하고 -> 9,7 전깃줄과 10,10 전깃줄은 겹치지 않으므로 아까 구한 LIS 길이에 1을 더해 2가 됩니다.

같은 방법으로 (4,1), (6,4), (7,6), (9,7), (10,10) 까지는 전깃줄이 겹치지 않고 LIS길이가 계속 늘어 5가 됩니다.

이 상태에 (3,9) 전깃줄을 추가하면 겹치는 부분이 발생하게 됩니다.

겹치는 영역은 (4,1), (6,4), (7,6), (9,7) 네 전깃줄로 (3,9)와 공존이 가능한 전깃줄은 (10,10) 뿐이고 그때의 LIS 길이에 1을 더한 2가 (3,9)를 포함한 LIS의 길이가 됩니다.

 

 

같은 방법으로 (2,2)를 추가했을때는 (2,2)다음으로 올 수 있는 전깃줄이 (6,4)로 (6,4)때 구한 값 4에 1을 더한 5를 얻고

(1,8)을 추가했을때는 (1,8), (3,9), (10,10)의 LIS가 구해집니다.

모든 경우에서 최댓값을 찾으면 예제에서 구할 수 있는 LIS의 길이는 5로 두가지 경우인 것을 알 수 있습니다.

 

이를 코드로 구현하면,

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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[][] wires = new int[N][2];

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

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

		int[] dp = new int[N];

		for (int n = N - 1; n >= 0; n--) {
			dp[n] = 1;
			int end = wires[n][1];
			for (int m = n; m < N; m++) {
				if (wires[m][1] > end) {
					dp[n] = Math.max(dp[n], 1 + dp[m]);
				}
			}
		}

		int max = 0;

		for (int n = 0; n < N; n++) {
			max = Math.max(max, dp[n]);
		}

		System.out.println(N - max);

	}
}

이렇게 작성 할 수 있을것 같습니다. 감사합니다.

곧 전깃줄2 문제도 풀도록 하겠습니다.

728x90

+ Recent posts