안경잡이개발자

728x90
반응형

문제 유형: 그리디

문제 URL: https://codeforces.com/contest/1075/problem/C


  문제를 간단히 요약하자면 다음과 같습니다.


  높이고 10^9이고, 너비가 10^9인 체스판이 있습니다. 이 때 가장 왼쪽 아래인 (1, 1)의 위치에 하나의 돌이 있습니다. 얘는 마차(Look)라서 이동할 때 상하좌우로 쭉쭉 이동할 수 있습니다. 이 돌은 체스판의 가장 위쪽에 도달하고자 합니다. y 좌표 상으로 10^9의 위치에 닿으면 되는 것이며 x 좌표는 어떤 값이 들어가도 상관 없습니다. 좌표를 나타낼 때는 (열, 행)과 같은 방식으로 표현합니다.


  이 때 체스판을 가로 막는 다양한 선들이 있다고 합니다. 선의 종류로는 수직선과 수평선이 있습니다.


  1) 수직선: 특정한 x 위치에서 수직으로 끝 없이 이어진 선입니다.

  2) 수평선: x1부터 x2까지의 열을 차지하는 선으로, 행 y에 위치합니다.


  수평선들은 수직 관계에 있는 다른 선들과는 x 좌표가 겹쳐도 됩니다. 하지만 수평한 수평선끼리는 x 좌표가 겹치지 않는다고 합니다. (1, 1)에 위치한 돌은 y 좌표 상으로 10^9의 위치에 닿을 때까지 이동할 수 있는데, 체스판에 있는 선들을 뚫고 나아갈 수 없다고 합니다. 따라서 선으로 가로 막힌 경우 선을 지우고 나아가야 합니다. 체스판의 가장 위쪽까지 도달하도록 선을 삭제할 때 최소한의 삭제할 선 개수를 구하면 됩니다.


※ 핵심 풀이 ※


  이 문제는 두 개의 사실만을 깨달으면 쉽게 풀 수 있고, 깨닫지 못하면 푸는 것이 굉장히 어렵습니다.


  ▶ 그것은 바로 수평선 중에서 왼쪽 x 좌표가 1이 아닌 것은 무시해도 된다는 것입니다.

  ▶ 그로 인해 수평선의 y 좌표는 신경 쓸 필요가 없다는 것까지 유추하면 됩니다.


  수평선의 왼쪽 x 좌표가 1이 아닌 것은 무시해도 좋은 이유를 설명해드리겠습니다. 이것은 '수평한 수평선끼리는 x 좌표가 겹치지 않는다'는 성질 때문에 가능한 것입니다.


  다음과 같은 경우를 생각해봅시다.



  몇 개의 선을 삭제해야 제일 위 칸으로 이동할 수 있을까요?


  정답은 바로 1개의 선입니다.



  위와 같이 중간에 있는 선을 지워버리면, 지그재그로 이동하여 제일 위 칸까지 이동할 수 있거든요. 결과적으로 왼쪽 x 좌표가 1인 수평선이 아니면 사실상 전혀 의미 없는 수평선이라고 할 수 있습니다. 돌 입장에서는 왼쪽 끝까지 편하게 이동할 수 있으니까요.



  결과적으로 기존의 시작할 때의 상태는 왼쪽 x 좌표가 1이 아닌 수평선들은 모두 지워버린 위 그림과 같은 상태와 같다고 볼 수 있습니다. 이렇게 정리된 상태에서 보니 한 가지 더 알게 되는 점이 있습니다. 그것은 바로 y 좌표는 굳이 신경 쓸 필요가 없다는 것입니다. 왜냐하면 어차피 하나의 y 좌표에는 최대 1개의 수평선만이 존재할 수 있을 테니까요. y 좌표는 고려 할 필요가 없습니다.


  이러한 원리를 이용하여, 각 수직선을 왼쪽부터 차례대로 확인하며 위를 덮는 수평선의 개수를 고려하여 정답을 도출하면 됩니다.


※ 예시 입출력 ※


input
Copy
2 3
6
8
1 5 6
1 9 4
2 4 2
output
Copy
1
input
Copy
1 3
4
1 5 3
1 9 4
4 6 6
output
Copy
1
input
Copy
0 2
1 1000000000 4
1 1000000000 2
output
Copy
2
input
Copy
0 0
output
Copy
0
input
Copy
2 3
4
6
1 4 3
1 5 2
1 6 5
output
Copy
2


※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include 
#include 
#define MAX 100001

using namespace std;

int vertical[MAX], line[MAX];
int INF = 1e9;

int main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> vertical[i];
	vertical[n++] = INF;
	sort(vertical, vertical + n);
	int lineCount = 0;
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c; 
		if (a != 1) // 왼쪽 x 좌표가 1인 수평선은 무시
			continue;
		line[lineCount++] = b;
	}
	sort(line, line + lineCount);
	int res = lineCount; // 시작 위치에서 돌이 위쪽으로만 뚫고 이동하는 경우를 초기 값으로 설정 
	int j = 0;
	// 각 수직선을 왼쪽부터 하나씩 확인하며 
	for(int i = 0; i < n; i++) {
		// 각 수직선을 덮는 수평선들의 개수를 세기 
		while (j < lineCount && line[j] < vertical[i]) {
			j++;
		}
		res = min(res, i + lineCount - j);
	}
	cout << res;
	return 0;
}


728x90
반응형

728x90
반응형

문제 유형: 그리디

문제 URL: https://codeforces.com/contest/915/problem/C


  이 문제는 특정한 수가 주어졌을 때 그 수로 순열을 처리하는 문제입니다. 두 수 a와 b가 있다고 합시다. 이 때 a로 만들 수 있는 자릿수의 순열 중에서 b보다 크지 않은 가장 큰 수를 구해 출력하는 문제입니다. 입력과 출력으로는 0으로 시작하지 않는 양의 정수가 입력 됩니다. 이 때 자릿수의 순열이란, 수에서 숫자들의 자리를 서로 바꾸어 나타낼 수 있는 수들을 의미합니다.


  b보다 크지 않은 가장 큰 수를 구해야 하므로 맨 왼쪽부터 가장 큰 숫자가 나올 수 있도록 하나씩 숫자를 배정하면 문제를 해결할 수 있습니다. 이 때 가장 중요한 것은 단순히 들어갈 수 있는 가장 큰 숫자를 넣는다고 되지는 않습니다. 그렇게 하면 답을 못 구할 수도 있어요. 숫자를 하나씩 넣을 때마다 최소 크기 접미사를 붙여서 b보다 작은지 검사하는 로직이 추가적으로 필요합니다.


  a: 123456789123456789

  b: 276193619183618162


  왜 최소 크기 접미사를 구해야 하는지는 위의 예시를 통해 확인할 수 있습니다.


  단순히 들어갈 수 있는 가장 큰 숫자를 계속해서 배정하면 '276193619'에서 더이상 진행할 수 없습니다. 그 뒤에 오는 b의 숫자가 1이므로, 문자열 a에 포함된 숫자 중에서 넣을 수 있는 1보다 작거나 같은 숫자는 더 이상 존재하지 않기 때문이에요. 그러므로 9 대신 그 다음 작은 숫자인 8이 들어가서 '2761936189~'로 진행되는 방식으로 처리해야 합니다. 이를 효과적으로 판단하기 위해서 최소 크기 접미사를 넣어보는 겁니다.


  9를 넣는 경우와 8을 넣는 경우를 비교해봅시다. 왼쪽의 수는 우리가 찾을 해답이고, 오른쪽에 있는 수는 b를 의미합니다.


  276193619234455788 > 276193619183618162 (불가능)

  276193618234455789 < 276193619183618162 (가능)


  9를 넣는 경우와 8을 넣는 경우 각각에 대해서 최소 접미사를 붙인 경우는 위와 같습니다. 9가 들어가는 경우에는 최소 크기 접미사를 붙였을 때, b보다 더 커지므로 불가능한 것입니다. 반면에 그보다 더 작은 숫자인 8부터 다시 넣어서 최소 크기 접미사를 붙여보니 b보다 작거나 같으므로 8은 들어갈 수 있는 것입니다. 결과적으로 기본적으로 왼쪽부터 최대한 큰 숫자를 채워 넣고, 해당 숫자가 들어갈 수 있는 지의 여부는 최소 접미사를 통해 확인할 수 있는 것입니다.


※ 예제 입출력 ※

input
Copy
123
222
output
Copy
213
input
Copy
3921
10000
output
Copy
9321
input
Copy
4940
5000
output
Copy
4940


※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#define MAX 10

using namespace std;

string a, b;
int d[MAX];
string res;

// 남은 뒷 자릿들을 '가장 작은 수'가 되도록 채웁니다. 
void makeSmall(int from)
{
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < d[i]; j++)
			res[from++] = i + '0';
}

int main()
{
	cin >> a;
	cin >> b;
	for (int i = 0; i < a.length(); i++)
		d[a[i] - '0']++;
	int zeros = 0;
	// A가 B보다 자릿수가 작은 경우 앞에 0을 채웁니다. 
	while (a.length() < b.length()) {
		a = "0" + a;
		zeros++;
	}
	res = a;
	// '원래 A의 길이'만큼 반복합니다. 
	for (int i = zeros; i < a.length(); i++) {
		// 9부터 0까지의 숫자 중에서 들어갈 수 있는 것을 고릅니다. 
		for (int j = MAX - 1; j >= 0; j--) {
			// 일단 넣어 봅니다. 
			if (d[j] > 0) {
				d[j]--;
				res[i] = j + '0';
				// 현재 넣은 숫자를 토대로 뒷자리들은 최대한 작게 구성합니다.
				// 이렇게 만들어진 수가 가능한 수라면 break;하여 해당 자릿수 구성을 완료합니다. 
				makeSmall(i + 1);
				cout << i << ":" << res << '\n';
				if (res <= b) break;
				d[j]++;
			}	
		}
	}
	// 앞에 들어가는 0은 무시하고 출력합니다. 
	int pos = 0;
	while (res[pos] == '0') pos++;
	cout << res.substr(pos);
	return 0;
}


728x90
반응형

728x90
반응형

문제 유형: 구현

문제 URL: https://codeforces.com/contest/1075/problem/B


  끝 없이 이어지는 좌표 상의 선으로 구성된 도시가 있습니다. 이 중에서 매일 도시 거주자들을 태워주는 M명의 택시 기사가 있습니다. 전체 구성원은 N명입니다. 택시 기사를 포함해 모든 N명의 사람들은 고유한 위치에 거주하고 있습니다.


  어떠한 사람이 택시를 부르면, 모든 택시 기사에게 전화를 하는 것이 아니라 자신과 가장 가까운 택시 기사 한 명만 부르게 됩니다. 만약에 거리가 동일한 택시기사가 여러 명이라면, 좌표 상에서 가장 작은 위치를 가진 택시 기사를 부르게 됩니다.


  어느 날 아침에, 택시 기사들은 하나의 의문이 생겼습니다. "매일 각 택시 기사들은 몇 명에게 전화를 받을까?"입니다. 이에 대한 답을 알려주는 프로그램을 작성하면 됩니다.


  예를 들어 일반 주민이 3명, 택시기사가 3명이라고 해봅시다. 이러면 전체 사람이 6명이므로 각각 위치가 주어지고, 각 위치에 따라서 해당 사람이 택시기사라면 1을, 아니라면 0이도록 입력이 주어지는 것입니다.


  전체 사람들의 위치: 2 3 4 5 6 7

  택시 기사들의 위치: 1 0 1 0 1 0


  이 때 택시 기사 3명은 각각 1명씩 전화를 받게 됩니다. 3번 위치의 사람은 2번 위치의 택시 기사에게, 5번 위치의 사람은 4번 위치의 택시 기사에게, 7번 위치의 사람은 6번 위치의 택시 기사에게 말입니다.


  이 문제는 간단히 크기가 2인 슬라이딩 윈도우를 이용해 풀 수 있습니다. 택시기사를 앞에서부터 두 명씩 묶어서 확인하면 돼요. 모든 사람들에 대해서 한 명씩 확인을 하는 건데요. 왼쪽 기사와 오른쪽 기사 사이에 있는 사람은, 더 가까운 기사에게 전화를 걸도록 처리하면 됩니다. 더 뒤쪽에 있는 택시기사의 위치보다 현재 사람의 위치가 크다면 슬라이딩을 수행하여, 그 이후의 택시기사 2명을 보는 방식을 사용합니다.


※ 입출력 예시 ※


input
Copy
3 1
1 2 3 10
0 0 1 0
output
Copy
3 
input
Copy
3 2
2 3 4 5 6
1 0 0 0 1
output
Copy
2 1 
input
Copy
1 4
2 4 6 10 15
1 1 1 1 0
output
Copy
0 0 0 1 

※ 정답 소스코드 ※
(컴파일 환경: GNU G++11 5.1.0)
#include <iostream>
#include <vector>

using namespace std;

vector a;
vector taxi;
vector res;

int main(void) {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n + m; i++) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	for(int i = 0; i < n + m; i++) {
		int x;
		cin >> x;
		if(x == 1) {
			taxi.push_back(a[i]);
			res.push_back(-1); // 택시 기사도 주민으로 보므로 초기에 -1로 설정 
		}
	}
	// 택시 기사가 1명이면, 크기가 2인 윈도우를 만들 수 없어 바로 답 출력 후 종료 
	if(taxi.size() == 1) {
		cout << a.size() - 1;
		return 0;
	}
	int now = 0;
	int start = taxi[now];
	int end = taxi[now + 1];
	for(int i = 0; i < a.size(); i++) {
		while(a[i] > end) {
			// 범위 한 칸 슬라이드 
			now++;
			// 마지막 범위인 경우 
			if(now == taxi.size() - 1) {
				// 남은 주민들을 마지막 택시에게 배정하고 종료 
				res[now] += a.size() - i;
				break;
			}
			start = taxi[now];
			end = taxi[now + 1];
		}
		if(now == taxi.size() - 1) break;
		// 현재 주민이 왼쪽과 가까운지, 오른쪽과 가까운지 판별 
		if(a[i] - start <= end - a[i]) {
			res[now]++;
		}
		else {
			res[now + 1]++;
		}
	}
	for(int i = 0; i < res.size(); i++) {
		cout << res[i] << ' ';
	}
	return 0;
}


728x90
반응형

728x90
반응형

문제 유형: 구현

문제 URL: https://codeforces.com/contest/1075/problem/A


  N x N의 체스 판이 있을 때 (1, 1)에 '화이트 킹'이 있고, (N, N)에 '블랙 킹'이 있습니다. 각 킹은 인접한 8가지 방향의 셀 중 한 곳으로 이동할 수 있습니다. 대각선도 포함해 이동할 수 있는 것입니다. 이 때 (X, Y)의 위치에 화이트 킹과 블랙 킹 중에서 누가 더 먼저 도착할 수 있는지를 구하면 되는 문제입니다. 다만 화이트 킹이 먼저 이동하며 시작과 동시에 킹의 위치와 (X, Y)가 동일하다면 그 즉시 종료됩니다.


  이 문제는 매우 간단한 문제입니다. (1, 1)에 화이트 킹이 있으며 (N, N)에 블랙 킹이 있으므로, 두 위치에서 (X, Y) 까지의 이동 횟수를 구하면 됩니다. 횟수를 구할 때는 각 킹들이 대각선 방향으로도 이동할 수 있다는 점에서 '가로 길이와 세로 길이 중에서 더 긴 것'을 구하면 됩니다.


  이동 횟수: 가로 길이와 세로 길이 중에서 더 긴 것


  결과적으로 이동 횟수를 비교하여 정답을 출력하면 됩니다.


※ 입출력 예시 ※


input
Copy
4
2 3
output
Copy
White
input
Copy
5
3 5
output
Copy
Black
input
Copy
2
2 2
output
Copy
Black


※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <stdio.h>

using namespace std;

int main(void) {
	long long int n;
	cin >> n;
	long long int x, y;
	cin >> x >> y;
	long long int black = max(n - x, n - y);
	long long int white = max(x - 1, y - 1);
	if(black == 0) {
		cout << "Black";
	}
	else if(white == 0) {
		cout << "White";
	}
	else if(white <= black) {
		cout << "White";
	}
	else {
		cout << "Black";
	}
	return 0;
}


728x90
반응형

728x90
반응형

문제 유형: 수학

문제 URL: https://codeforces.com/contest/915/problem/A


  정원은 길이가 K인 선분(Segment) 형태로 표현됩니다. 또한 N개의 그릇에 물을 담아서 농작물에 물을 주려고 합니다. i번째 그릇은 한 시간에 Ai 길이의 연속적인 공간에 물을 줄 수 있도록 해줍니다. 이 때 한 번 물을 준 곳은 더 이상 주지 않으며 주인공은 하나의 그릇을 선택하여 가능한 빠르게 농사를 짓는 전체 공간에 물을 주고자 합니다. 이 때 주인공이 가장 적은 시간으로 정원에 물을 줄 때의 시간을 구하면 됩니다.


  이 문제는 길이가 K인 전체 정원에 물을 주어야 하며 남는 공간이 없어야 하고, 한 번 물을 준 곳은 더 이상 줄 수 없다는 점에서 단순히 약수를 판별하는 문제입니다. 주어진 그릇의 크기 중에서 K의 약수로 가장 큰 것을 고르면 됩니다. 따라서 K를 해당 약수로 나눈 값을 출력하도록 하면 정답 처리를 받을 수 있습니다. 또한 항상 하나 이상의 그릇은 정원의 모든 공간에 물을 줄 수 있도록 입력이 주어진다고 합니다.


※ 예시 입출력 ※

input
Copy
3 6
2 3 5
output
Copy
2
input
Copy
6 7
1 2 3 4 5 6
output
Copy
7


※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <limits.h>

using namespace std;

int main(void) {
	int n, k;
	cin >> n >> k;
	int res = INT_MIN;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if(k % x == 0) {
			res = max(res, x);
		}
	}
	cout << k / res;
	return 0;
}


728x90
반응형

728x90
반응형

문제 유형: 구현

문제 URL: http://codeforces.com/contest/399/problem/A


  이 문제는 구현의 끝판왕 문제인 게시판 페이징(Paging) 문제입니다. 전체 페이지의 개수를 N, 현재 페이지를 P, 현재 페이지를 기준으로 왼쪽과 오른쪽에 몇 개의 페이지까지 표시할 지를 K라고 합니다. 이 때 << 3 4 (5) 6 7 >>와 같은 방식으로 페이징 처리를 하면 됩니다.


  왼쪽으로 페이지가 더 남았을 때는 "<<"를 출력하고, 오른쪽으로 페이지가 더 남았을 때는 ">>"를 출력합니다. 실제 게시판을 구현할 때도 비슷한 방식의 페이징 처리 알고리즘 구현해 본 경험이 있다는 점에서 재미있게 풀 수 있었습니다.


※ 예시 입출력 ※


input

17 5 2

output

<< 3 4 (5) 6 7 >> 

※ 정답 소스코드 ※
(컴파일 환경: GNU G++11 5.1.0)
#include <iostream>
#include <stdio.h>

using namespace std;

int main(void) {
	int n, p, k;
	cin >> n >> p >> k;
	// 왼쪽으로 이동이 가능한 경우 
	if(p - k > 1) {
		cout << "<< ";
	}
	for(int i = ((p - k > 1)? p - k : 1); i < p; i++) {
		cout << i << ' ';
	}
	// 현재 페이지를 출력 
	cout << "(" << p << ") ";
	for(int i = p + 1; i <= ((p + k < n)? p + k : n); i++) {
		cout << i << ' ';
	}
	// 오른쪽으로 이동이 가능한 경우 
	if(p + k < n) {
		cout << ">>";
	}
	return 0;
}


728x90
반응형

728x90
반응형

문제 유형: 수학

문제 URL: http://codeforces.com/contest/393/problem/A


  이 문제는 특정한 문자열이 주어졌을 때 그 문자열의 문자들을 재정렬해서 "nineteen"이라는 문자열을 몇 개나 만들 수 있는지 물어보는 문제입니다. 예를 들어 문자열 "xiineteenppnnnewtnee"이 주어졌을 때 이를 "xnineteenppnineteenw"와 같이 재정렬한다면 "nineteen" 문자열이 두 번 나오게 되는 것입니다. 따라서 위 경우 최대 2개 만들 수 있으므로 정답은 2입니다.


  또한 "nineteen"이라는 문자열의 개수를 셀 때는 전체 문자열을 앞에서부터 한 자씩 읽어 확인하므로 문자를 읽다가 건너 뛸 수 없습니다. 또한 문자 n은 끝과 시작이 이어질 수 있습니다. 예를 들어 "nineteenineteen"과 같이 나열하면 n의 개수가 5개여도 "nineteen"을 2번 찾을 수 있습니다.


  이 문제는 단순히 n, i, e, t 문자의 개수를 세서 풀 수 있습니다. "nineteen"은 n 3개, i 1개, e 3개, t 1개로 이루어집니다. 따라서 만들 수 있는 "nineteen"의 최대 개수를 구하기 위해서는 각 문자를 몇 개씩 가지고 있느냐를 기준으로 개수를 찾을 수 있을 것입니다. 특히 n은 끝과 시작이 이어질 수 있기 때문에 사실상 n은 2개만 있어도 하나의 "nineteen"을 구성할 수 있다고 고려해야 합니다.


※ 정답 소스코드 ※


(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#include <stdio.h>
#include <limits.h>

using namespace std;

int main(void) {
	int nC = 0;
	int iC = 0;
	int eC = 0;
	int tC = 0;
	string input;
	cin >> input;
	for(int i = 0; i < input.size(); i++) {
		if(input[i] == 'n') nC++;
		else if(input[i] == 'i') iC++;
		else if(input[i] == 'e') eC++;
		else if(input[i] == 't') tC++;
	}
	int res = INT_MAX;
	if(nC > 3) {
		// n은 끝과 시작이 이어질 수 있습니다. 
		res = min(res, (nC - 1) / 2);
	}
	else {
		res = min(res, nC / 3);
	}
	res = min(res, iC);
	res = min(res, tC);
	res = min(res, eC / 3);
	cout << res;
	return 0;
}


728x90
반응형