[BOJ] 백준 6417 JS

백준 / 6417 / JS / Brute-force

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

문제

1926년 10월 9일의 신문엔 미국의 유명 극작가 벤 윌리암스의 짤막한 문제 하나가 실렸다. 전문은 다음과 같다.
다섯 명의 남자가 무인도에 갇혔다. 그들은 표류 첫 날, 하루 종일 힘을 합쳐 코코넛을 모았다.
그날 밤 첫 사람이 일어나 코코넛을 세어보니 하나를 빼면 정확히 5등분을 할 수 있었다.
그래서 지나가던 원숭이에게 코코넛 하나를 주고 나머지를 5등분하여 자기 몫의 한 무더기를 숨겨 두고 잠들었다.
그리고 바로 그 직후, 두 번째 사람이 일어나 코코넛을 세어보니 하나를 빼면 정확히 5등분을 할 수 있었다.
그래서 지나가던 원숭이에게 코코넛 하나를 주고 나머지를 5등분하여 자기 몫의 한 무더기를 숨겨 두고 잠들었다.
그 바로 다음 세 번째 사람도, 네 번째 사람도, 다섯 번째 사람도 같은 일을 했다.
이제 잠에서 깬 다섯 명이 남은 코코넛을 세어 보니 정확히 5등분을 할 수 있었다.
그래서 그들은 남은 코코넛을 5등분하여 한 묶음씩 가졌다.
이때, 그들이 처음 모은 코코넛은 모두 몇 개였을까?
문제의 답은 사실 무수히 많다. 하지만 그 중 가장 작은 수는 3121개이다.
하지만 이 문제는 우리가 풀 문제가 아니다.
우리는 코코넛 이야기를 반대로 생각해보기로 하자.
처음 모은 코코넛이 N개였고, 위의 규칙대로 K명의 사람들이 코코넛을 다들 나누어 가지는 데 성공했다면, 이때 K는 최대 몇이 될 수 있을까?

입력

입력은 여러 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫 줄엔 문제의 N이 주어지며, N이 -1일 경우 입력의 종료를 의미한다.

출력

각 N에 따라 한 줄에, K가 존재할 경우 "N coconuts, max(K) people and 1 monkey" 를,
어떤 K도 코코넛을 규칙대로 나눌 수 없을 경우 "N coconuts, no solution"을 출력한다.

풀이

처음 문제를 읽고 K를 찾기 위해 단순 반복을 하면 시간 초과가 뜨지 않을까 싶었다
1<= N <= 1,000,000, O(n)
2<= K <= 1,000,000 (대충 생각하기에 N보다 작을 때 까지) O(n)
총 O(N^2)이 나오지 않을까 싶었지만 반복문 종료 조건이 많은 필터링을 거쳐지기 때문에 시간초과가 뜨진 않은 것 같다.

let input = require('fs')
  .readFileSync(__dirname + '/input.txt', { encoding: 'utf-8' })
  .split('\n');
let n = input.shift();
let k = 2;
let answer = []; // k값들을 저장할 배열
while (true) {
  if (n === '-1') {
    // 종료 조건
    break;
  }
  let coconut = parseInt(n);
  while (k < coconut) {
    // k가 최대값이 되기 위해 coconut보다 작을 때 까지 탐색
    for (let i = 0; i < k; i++) {
      coconut -= 1; // 원숭이에게 한 개
      coconut -= coconut / k; // 내 몫을 제외하고 나머지
      if ((coconut - 1) % k !== 0) {
        // 나누어지는지 확인
        if (i === k - 1) {
          answer.push(k);
        }
        break;
      }
    }
    k++; // 재탐색을 위한 초기화
    coconut = parseInt(n);
  }
  if (answer.length !== 0) {
    // k값이 있을때 없을 때 구분
    console.log(
      n,
      'coconuts,',
      answer[answer.length - 1],
      'people and 1 monkey'
    );
  } else {
    console.log(n, 'coconuts, no solution');
  }
  answer = []; // 초기화
  k = 2;
  n = input.shift();
}