[코드포스/Virtual] Codeforces Round #620 (Div. 2)

클릭하면 코드포스 페이지로 이동합니다.

 

---

 

#620 후기

 

문제 A는 빠르게 풀었는데, 문제 B에서 이상하게 생각하다가 시간놓치고, 문제 C에서 생각을 잘못했는지 구현을 실수했는지 내리 3번 틀려버렸다.. 생각보다 문제 자체는 풀만했는데, 내가 아직 많이 부족하고, 좀 더 많은 문제를 풀어봐야겠다고 생각이 들었다.

 

---

 

#620 문제

  A번 Two Rabbits - 성공

#620 A번 Two Rabbits

 

좌표 x에 있는 토끼가 1초에 오른쪽으로 a씩, 좌표 y에 있는 토끼가 1초에 왼쪽으로 b씩 이동한다.
몇 초 뒤에 두 토끼가 만날 수 있으면, 필요한 시간을 출력하고, 만나지 못한다면 -1을 출력한다.

 

걸리는 시간을 T초 라고 생각하면, 각각의 토끼의 위치는

 

좌측토끼 : x + a * T

우측토끼 : y - b * T

 

로 표현된다.

 

시간이 1초, 2초, ... 로 흐르므로, 한 지점에서 만날 수 있다는 것은 두 토끼의 위치가 같다는 의미이고,

이는 곧 두 토끼의 거리의 차 (y - x)가 (a + b)로 나누어 떨어진다는 것을 의미한다.

 

코드로 간단하게 구현이 가능하다.

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main(void){
	// For fast IO
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;

	cin >> tc;

	while(tc--) {
		ll x, y, a, b;
		cin >> x >> y >> a >> b;
		if((y - x) % (a + b) == 0) {
			cout << (y - x) / (a + b) << "\n";
		} else {
			cout << "-1\n";
		}
	}

	return 0;
}

---

  B번 Longet Palindrome - 성공

길이가 m인 문자열 n개를 이용하여 가장 긴 길이의 펠린드롬(앞에서부터 읽은 문자열과 뒤에서부터 읽은 문자열이 같은 문자열)이 되도록 만들어라. 그때의 문자열의 길이와 문자열을 출력하라.

 

처음에 모든 경우를 다 탐색해볼까 하다가, 펠린드롬은 맨 앞과, 맨 뒤를 제외한 가운데 부분도 펠린드롬이라는 생각이 들었다.

 

그리고 문자열의 개수가 많지 않기 때문에, 모든 문자열을 확인하면서 두개가 펠린드롬인 문자가 있으면, 먼저 출력할 문자는 큐에, 뒤에 출력할 문자는 스택에 저장한다.

 

이런식으로 짝을 찾아서 저장하고, 짝이 없는 문자열 중에서, 자기 자신이 펠린드롬인 문자열이 있으면, 그 문자열을 가운데에 출력할 수 있으므로, 확인해서 저장한다.

 

또한 이러한 과정 중에 펠린드롬의 길이가 증가할때마다 cnt 변수를 증가시켜서 마지막에 출력한다.

 

그래서 순서대로 큐에 있는 문자열들을 출력하고, 가운데에 있는 (없을수도 있다.) 문자열을 출력하고, 스택에 있는 문자열들을 출력하면 된다.

 

스택과 큐 대신에, 덱을 이용하면 어땠을까 하는 생각도 들고, 코드가 너무 난잡하다는 생각도 들지만, 처음에 이상하게 생각하다가 늦게 생각나서 빠르게 코딩해서 어쩔수 없다는 생각이 들고, 너무 늦게 생각난게 아쉽습니다.

 

코드로 구현하면

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int n, m, cnt = 0, mididx = -1;
string s;
vector<string> v;		// 문자열을 저장하는 벡터
vector<bool> isused;	// 이미 사용된 문자열인지 확인
queue<int> fans;		// 앞에서부터 출력할 문자열
stack<int> bans;		// 중간 이후부터 출력할 문자열


int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for(int i = 0; i < n; i++) {
		cin >> s;
		v.push_back(s);
		isused.push_back(false);
	}

	while(true) {
		bool havePair = false;
		for(int i = 0; i < n; i++) {		// 처음에 위치할 문자열
			for(int j = 0; j < n; j++) {	// 끝에 위치할 문자열
				if(i == j || isused[i] || isused[j] || havePair) continue;
				else {
					bool ispd = true;	// i와 j가 펠린드롬이면 true
					for(int idx = 0; idx < m; idx++) {
						int iidx = idx;
						int jidx = m - idx - 1;
						if(v[i][iidx] != v[j][jidx]) {
							ispd = false;
							break;
						}
					}

					if(ispd) {
						havePair = true;
						isused[i] = true;
						isused[j] = true;
						fans.push(i);
						bans.push(j);
						cnt += 2;
					} else {
						continue;
					}
				}
			}
		}

		if(!havePair) break;
	}

	for(int i = 0; i < n; i++) {
		if(!isused[i]) {
			bool ispd = true;
			for(int j = 0; j < m; j++) {
				// 자기자신이 펠린드롬인지 확인
				if(v[i][j] != v[i][m - j - 1]) {
					ispd = false;
					break;
				}
			}
			if(ispd) {
				mididx = i;
				cnt++;
				break;
			}
		}
	}
	
	// 출력
	cout << cnt * m << "\n";

	while(!fans.empty()) {
		cout << v[fans.front()];
		fans.pop();
	}
	if(mididx > -1) {
		cout << v[mididx];
	}
	while(!bans.empty()) {
		cout << v[bans.top()];
		bans.pop();
	}

	return 0;
}

 

---

C번 Longet Palindrome - 실패

손님들의 방문 횟수 n과 레스토랑의 초기 온도 m이 주어진다.
레스토랑은 1분마다 1. 온도를 유지하던가 / 2. 온도를 1도 증가시키거나 / 3. 온도를 1도 감소시킬 수 있다.
각각의 손님은 방문 시간과 최소 온도, 최대 온도를 가지고 있고, 레스토랑의 온도는 항상 이 온도 사이에 위치해야 한다.
손님들이 알맞은 온도에서 있을 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

 

대회 중에는 현재 온도에서 온도를 계속 낮췄을 경우 (최소온도), 온도를 계속 올렸을 경우 (최대온도)를 각각 구하고, 그 온도 내에 손님들의 적정 온도가 있으면 다음 손님도 검색하고를 반복하려고 했지만....

 

예제가 나와서 기쁜 마음에 제출했다가, 테스트케이스 3에서 3연벙 당한 덕분에 그대로 2 Solve로 종료했다..

 

다시 풀어보고 추후에 코드 추가하겠습니다.

 

추가) 입력 도중에 break로 입력이 밀려서 오류가 떴었습니다..

 

아래는 정답코드입니다.

 

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	cin >> tc;

	while(tc--) {
		ll n, m, curtime, curMinT, curMaxT;
		bool cansolve;

		cin >> n >> m;
		curtime = 0, curMinT = m, curMaxT = m, cansolve = true;

		for(int i = 0; i < n; i++) {
			ll t, l ,h, dif;
			cin>> t >> l >> h;
			
			dif = t - curtime;	// 최대 변경 가능한 온도
			curtime = t;

			if(h < curMinT) {
				if(h < curMinT - dif) {
					// 도달 불가능한 경우
					cansolve = false;
				} else {
					curMaxT = h;
					curMinT = max(curMinT - dif, l);
				}
			} else if(curMaxT < l) {
				if(curMaxT + dif < l) {
					cansolve = false;
				} else {
					curMinT = l;
					curMaxT = min(curMaxT + dif, h);
				}
			} else {
				curMinT = max(curMinT - dif, l);
				curMaxT = min(curMaxT + dif, h);
			}
		}
		if(cansolve) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}