취미로 코딩하기

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

이번에 볼 문제는 백준 25186번 문제인 INFP 두람이다.
문제는 아래 링크를 확인하자.

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

총 total개의 옷이 있고 그중 가장 많은 개수를 가진 옷 C의 개수를 K라 하자.

이 때 만약 K > total/2라면 어떻게 배치해도 C가 인접하게 배치될 수밖에 없다는 점을 관찰하자.

만약 그렇지 않다면 항상 모든 옷이 인접하지 않게끔 배치할 수 있다. 예를 들어 원형 리스트의 각 칸에서 한 칸씩 건너뛰면서 가장 많은 개수가 있는 옷부터 하나씩 채워넣는 식으로 배치하면(단, total이 짝수라면 한 바퀴를 돈 뒤 두 칸을 건너뛰고 나머지를 채운다) 모든 옷이 인접하지 않게끔 배치가 된다.

사람이 한 명만 있다면 서로 다른 두 명이 인접한 경우가 존재하지 않으므로 Happy를 출력해야하는 점을 잊지 말자.

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

#include <iostream>
using namespace std;
typedef long long ll;

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

	int N; cin >> N;
	ll mx = 0, total = 0;
	for (int i = 0; i < N; i++) {
		ll x; cin >> x;
		mx = max(mx, x);
		total += x;
	}
	
	if (mx <= total / 2) cout << "Happy";
	else cout << "Unhappy";
}