25245번 Amusement Arcade
문제
설계
n개의 오락기가 있다.(n은 홀수)
사람이 앉아야하는데 반드시 오락기에 한 칸씩 비우고 앉아야한다.
도착하는 사람은 사람이 있는 곳에서 가장 멀리 떨어진 자리를 고르며, 여러개라면 무작위로 선택한다.
이때 줄리아가 가장 먼저 앉을 적절한 위치를 고르시오.
n은 반드시 홀수고 한 칸씩 비우면 최대 인원은 (n + 1) / 2 이다.
줄리아가 대충 n / 2 + 1 위치인 중앙에 앉으면 impossible이 나올 조건은 없어보이는데…
예제에서는 15를 넣을 시 impossible이 나온다.
사람에서 최대한 멀리 떨어진 곳에 앉으려는 좋지 않은 습성 때문인데…
실제 15를 받아 줄리아를 8번에 앉힐 경우
[1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1]
이 상황에서 정확히 한 칸 조건이 깨져버린다!
구현
1. 시뮬레이션
제한시간이 빡빡해서 단순 시뮬레이션은 아닌 것 같다.
일단 대충 코드짜서 순열 규칙 확인 ㄱㄱ
줄리아의 자리는 모든 홀수 자리를 탐색해서 앉혀본다.
단순히 n / 2 + 1 에만 앉을 경우 7을 넣으면 4에 앉아야 하는데 그러면 오답이 나온다.
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
using namespace std;
int simulate(int n) {
int max = (n + 1) / 2;
int where = -1;
for (int k = 0 ; k < n ; k+=2) {
bool result = true;
vector<int> seats(n, 0);
// 줄리아가 앉을 자리
seats[k] = 1;
int people = 1;
while (people < max) {
// 현재 가능한 자리들 중 가장 큰 최소 거리
int max_dist = -1;
vector<int> candidates;
for (int i = 0 ; i < n ; i++) {
if (seats[i] == 1) {
continue;
}
int dist = numeric_limits<int>::max();
for (int j = 0 ; j < n ; j++) {
if (seats[j] == 1) {
// 가장 가까운 사람과의 거리
dist = min(dist, abs(i - j));
}
}
// 현재 자리가 이전보다 더 멀리 떨어져 있다면 새로운 후보, 같으면 추가
if (dist > max_dist) {
max_dist = dist;
candidates.clear();
candidates.push_back(i);
} else if (dist == max_dist) {
candidates.push_back(i);
}
}
// 후보자리가 없으면 끝
if (candidates.empty()) {
break;
}
for (int i = 0 ; i < candidates.size() ; i++) {
if (candidates[i] % 2 != 0) {
// 홀수 자리에 앉지 못하면 의미 없음
continue;
}else {
seats[candidates[i]] = 1;
break;
}
}
people++;
}
// 최종 상태가 x . x . x ... 패턴인지 확인
for (int i = 0 ; i < n ; i++) {
if (i % 2 == 0) {
if (seats[i] != 1) {
result = false;
break;
}
} else {
if (seats[i] != 0) {
result = false;
break;
}
}
}
if (result) {
where = k + 1;
break;
}
}
return where;
}
int main() {
bool result = false;
for (int i = 1 ; i <= 31 ; i+=2) {
cout << i << " : " << simulate(i) << endl;
}
return 0;
}
시뮬레이션 결과는 아래와 같다.
| n | 줄리아 |
|---|---|
| 1 | 1 |
| 3 | 1 |
| 5 | 1 |
| 7 | 3 |
| 9 | 1 |
| 11 | 3 |
| 13 | 5 |
| 15 | impossible |
| 17 | 1 |
| 19 | 3 |
| 21 | 5 |
| 23 | impossible |
| 25 | 9 |
| 27 | impossible |
| 29 | impossible |
| 31 | impossible |
예제는 다 맞는다.
2. 규칙 찾기
가설 1: n = 2^k + 1 (k > 0) 인 경우 답은 반드시 1이다.
| n | 줄리아 |
|---|---|
| 3 | 1 |
| 5 | 1 |
| 9 | 1 |
| 17 | 1 |
가설 2: n != 2^a + 2^b + 1 인 경우 배치가 불가능하다.
| n | 줄리아 |
|---|---|
| 15 | impossible |
| 23 | impossible |
| 27 | impossible |
| 29 | impossible |
| 31 | impossible |
이부분은 n + 1의 이진수 1의 개수가 3 이상이면 불가능으로 처리할 수 있다.
가설 3: 그 외의 경우는 시뮬레이션을 하되, 2^k + 1 인 자리만 대상으로 한다.
| n | 줄리아 |
|---|---|
| 7 | 3 |
| 11 | 3 |
| 13 | 5 |
| 19 | 3 |
| 21 | 5 |
| 25 | 9 |
2. 구현
가설 1, 2를 넘었을 경우 시뮬레이션을 해야하는데
n이 10^18까지 있으므로 평범하게 하면 바로 시간초과다.
어차피 꽉 채워 앉으면 완전 이진트리 구조가 되므로 줄리아 배치 기준 양쪽을 반으로 계속 나눌 수 있는지만 확인하면 된다.
// 가설 1: n == 2^k + 1 이면 반드시 줄리아는 1번 자리에 앉으면 됨
bool hypothesis_1(int64_t n) {
return (n > 1) && ((n - 1) & (n - 2)) == 0;
}
// 가설 2: n == 2^a + 2^b + 1 형태인지 확인
// n - 1 == 2^a + 2^b 라면 가능성 있음
bool hypothesis_2(int64_t n) {
int64_t x = n - 1;
int count = 0;
while (x > 0) {
if (x & 1) count++;
if (count > 2) return false;
x >>= 1;
}
return count == 2;
}
// 균등분할이 가능할지
bool can_seat(int64_t len) {
if (len < 2) return true;
if (len % 2 == 0) return false;
return can_seat((len - 1) / 2);
}
int64_t solve(int64_t n) {
// 짝수일 경우 패스
if (n % 2 == 0) {
return -1;
}
// 가설 1
if (hypothesis_1(n)) {
return 1;
}
// 가설 2
if (!hypothesis_2(n)) {
return -1;
}
// 가설 3
for (int i = 0 ; i < 64 ; i++){
int64_t pos = (1LL << i) + 1;
if (pos > n) {
break;
}
if (can_seat(pos - 2) && can_seat(n - pos - 1)) {
return pos;
}
}
return -1;
}
채점
허허 정답비율 나 혼자 다깎아먹었넹
반성
반복문 조건도 잘 못잡고 균등분할 조건도 잘 못잡고
제대로 했으면 덜 틀렸을걸 실컷 틀렸다.
아주 고봉밥이다 어우 배불러
근데 분명 더 멋진 풀이가 있을거란 말이지
맞힌 사람 보면 코드 길이가 심상치가 않다.
코드 확인