Parity

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27421 번역 문제 # Taro는 장난감 철도 선로 세트를 가지고 놀고 있습니다. 모든 선로는 직각 중심각(90도 각도)을 가진 호 모양이지만, 반지름은 다양합니다. Taro는 이 모든 선로를 사용하여 하나의 루프를 만들려고 합니다. 여기서 선로 세트가 하나의 루프를 형성한다는 것은 모든 선로의 양 끝이 다른 선로와 부드럽게 연결되고, 모든 선로가 직접 또는 간접적으로 다른 모든 선로와 연결되어 있을 때를 의미합니다. Taro가 이것을 달성할 수 있는지 여부를 알려주세요.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34830 🧐 관찰 및 접근 # 문제 상황을 차근차근 살펴보자 $a, b$가 있을 때, $a - b$ 를 한번 지나가면 된다. $a, b, c$가 있을 때, $a - b, b- c, c-a$를 한번씩 지나가야한다. $a, b,c ,d$가 있을 때, $a-b, a-c, a-d, b-c, b-d, c-d$를 한번씩 지나가야 한다. 이를 그래프 이론으로 해석할 수 있지 않을까? 그래프가 있고, 각 간선을 한번씩 지나되, 시점과 종점이 달라도 된다 한붓그리기가 가능한가? 이제 이 문제는 오일러 경로를 가능하게 하는 문제로 바뀐다. 오일러 경로는, 홀수점이 두개 이하일때 가능하다. 정점이 $N$개 있다고 하면, 그래프는 완전그래프이므로 각 정점에 붙어있는 간선은 $N-1$개이다. $N$이 홀수라면, 모든 $N$개의 정점은 짝수점이다. $N$이 짝수라면, 모든 $N$개의 정점은 홀수점이다. 따라서, $N-2$개의 점들을 연결해서 홀수점이 2개가 되도록 만드는것이 최적이다. 💻 풀이 # 코드 (C++): void solve(){ ll N; cin >> N; ll ans = N * (N-1) / 2; if(N%2 == 0) ans += N/2 - 1; cout << ans; }