취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24789번 문제인 Railroad이다.
문제는 아래 링크를 확인하자.

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

주어진 X-shaped level junction과 Y-shaped switch들을 먼저 바닥에 늘어놓고 다른 트랙을 이용해 이들을 이을 수 있는지를 판단하는 것으로 문제를 해결하자.

이 때, X-shaped level junction은 하나 추가될 때마다 이어야 할 끝점이 4개씩 늘어나고 Y-shaped switch는 하나 추가될 때마다 이어야 할 끝점이 3개씩 늘어난다. 한편, 각 끝점은 둘씩 짝지어 이을 수밖에 없으므로 끝점의 개수가 홀수인 경우 올바르게 트랙을 구성할 수 없다. 반면에 끝점의 개수가 짝수인 경우 "X-shaped level junction의 이웃한 두 끝점을 연결해 일반 레일처럼 사용하고 Y-shaped switch들을 일렬로 나열한 뒤 끝점을 하나씩 서로 이은 뒤 나머지를 아무렇게나 짝짓는 방법" 등으로 이들을 잇는 방법이 항상 존재하므로 항상 올바르게 트랙을 구성할 수 있다.

위 관찰을 이용해 식을 세워 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int x;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> x >> x;
	if (x & 1) cout << "impossible";
	else cout << "possible";
}