[ 백준 _ 15271 ] 번데기 by using JavaScript

문제

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

15721번: 번데기

 

How to Solve ?

 

문제를 이해 했는가?

 

번-데기-번-데기-번-번-데기-데기  -> ... -> 번-데기-번-데기-번*(n+1)-데기*(n+1)

 

번데기 게임은 다음과 같이 회차를 반복 할 수록 끝의 길이가 길어지는 게임이다. 이 때, "T번째 번 또는 데기를 누가 말했는지"찾아내는 프로그램을 만드시오.

 

처음에 "T번째 번 또는 데기" 를 말한 사람을 찾으라는 말을 들었을 때 이해가 잘 안됬는데 무슨 말인가 하면

 

"번-데기-번" 이 상황에서 뒤에 있는 "번"은 2번째로 사용된 수이며, 사람이 3명 이상 있었다면 3번째 사람이 "번"을 이야기 한 것임으로 "2"를 출력 해주면 된다.

 

알고리즘 종류 :  완전 탐색 

처음에는 규칙성을 찾으려고 했지만, 찾기가 어려워 주어진 "T"의 크기가 1만 밖에 되지 않아서 "n^2"으로 돌려도 1초면 해결 할 수 있는 문제라는 것을 알게 되었다. 그리하여, 완전 탐색을 이용 하기로 마음 먹었다.

 

어떻게 풀었는지?

완전탐색에는 다양한 종류가 있는데, 나는 "모든 케이스를 만들어 준 뒤, 그 중에서 값을 찾는 경우"를 브루트포스라고 부른다.

이 문제도 내 머리로는 브루트포스라고 여겨져, 일어날 수 있는 모든 가능성에 대해 만들어 주었다.

 

모든 상황을 미리 만들어 주려면, 최소한 그것과 관련된 규칙을 찾아야 하는데! 내가 찾은 규칙은 아래 보는 것처럼

 

1)  새로운 번데기 리듬이 시작되는 간격인 [0-8-18-30..]을 통해  [8-10-12-14] 처럼 2씩 증가 한다는 사실을 알게 되었다.

 

// 1번째 : 0

// 2번째 : 2 

// 3번째 : 4 

// 4번째 : 5 

 

// 5번째 : 8 

// 6번쨰 : 10 

// 7번째 : 12 

// 8번째 : 13 

// 9번쨰 : 14 

 

// 10번째 : 18 

// 11번째 : 20 

// 12번째 : 22 

// 13번째 : 23 

// 14번째 : 24 

// 15번째 : 25 

 

// 16번째 : 30 5

 

2) 새로운 번데기 리듬에서는 2씩 증가 하는 경우는 2번 존재한다.

 

3) 2번의 점프가 끝난 후, 1씩 더 하는 규칙은 매 회차마다 1번씩 늘어난다.

 

3가지의 규칙을 찾아 낼 수 있었다.

 

이를 통해, 뻔 배열과 데기 배열을 각각 [0,2,4,5], [1,3,6,7] 로 초기화를 해준 뒤 위의 패턴을 통해 10000번째까지의 수를 구해주었다.

  const bbun = [0, 2, 4, 5];
  const degi = [1, 3, 6, 7];

  // 다음 번데기 리듬까지와의 초기 거리
  let jump = 8;
  
  // 1을 몇 번 반복해서 더해주는지?
  let one_length = 2;
  
  // 번과 데기의 시작점
  let bbun_tmp = 0;
  let degi_tmp = 1;

  for (let i = 0; i < 137; i++) {
    // 시작점 + 점프 = 새로운 번데기 리듬의 시작점
    bbun_tmp += jump;
    degi_tmp += jump;
    // 다음 점프를 위해 2를 추가
    jump += 2;

    // 2씩 2번 더 해줌.
    bbun.push(bbun_tmp);
    bbun.push(bbun_tmp + 2);
    bbun.push(bbun_tmp + 4);
    // 2씩 2번 더 해줌.
    degi.push(degi_tmp);
    degi.push(degi_tmp + 2);
    degi.push(degi_tmp + 4);
	
    // 미리 저장해놓은 one_length 만큼 더 해준다.
    for (let j = 1; j <= one_length; j++) {
      bbun.push(bbun[bbun.length - 1] + 1);
      degi.push(degi[degi.length - 1] + 1);
    }
    // 1의 반복 값을 증가 시킨다.
    one_length += 1;
  }

  console.table(degi);

 

자 이렇게 코드를 작성하면, 아니 이렇게만 만들어 두면 "줄에 있는 어떤 사람이 그걸 한지 알아요?" 라는 의문이 들 수도 있다.

어차피 수가 엄청나게 늘어나도 번데기 게임은 원을 그리면서 이루어지기 때문에 원의 길이만큼 나눠주면 몇 번째 사람이 했는지 출력 할 수 있다.

 

전체코드

function solution() {
  const bbun = [0, 2, 4, 5];
  const degi = [1, 3, 6, 7];

  // 다음 번데기 리듬까지와의 초기 거리
  let jump = 8;

  // 1을 몇 번 반복해서 더해주는지?
  let one_length = 2;

  // 번과 데기의 시작점
  let bbun_tmp = 0;
  let degi_tmp = 1;

  for (let i = 0; i < 137; i++) {
    // 시작점 + 점프 = 새로운 번데기 리듬의 시작점
    bbun_tmp += jump;
    degi_tmp += jump;
    // 다음 점프를 위해 2를 추가
    jump += 2;

    // 2씩 2번 더 해줌.
    bbun.push(bbun_tmp);
    bbun.push(bbun_tmp + 2);
    bbun.push(bbun_tmp + 4);
    // 2씩 2번 더 해줌.
    degi.push(degi_tmp);
    degi.push(degi_tmp + 2);
    degi.push(degi_tmp + 4);

    // 미리 저장해놓은 one_length 만큼 더 해준다.
    for (let j = 1; j <= one_length; j++) {
      bbun.push(bbun[bbun.length - 1] + 1);
      degi.push(degi[degi.length - 1] + 1);
    }
    // 1의 반복 값을 증가 시킨다.
    one_length += 1;
  }

  if (b === 0) {
    console.log(bbun[t - 1] % a);
  } else {
    console.log(degi[t - 1] % a);
  }
}

 

느낀점

내가 가장 약한 부분은 "구현"이 맞는 것 같다. 주어진 요구사항대로 짜는 연습을 하고, 시간이 오래 걸려도 가능하면 구현은 꼭! 나의 힘으로 하고 만약 다른 사람의 코드를 참고 할거라면 "풀이법"만 가져오는게 좋을 것 같다.