돌 게임

문제

언어

  • JavaScript

순서도

  1. 홀수면 “SK” 출력, 짝수면 “CK” 출력

문제 풀이 step 1

  • 주어진 N 개의 돌을 상근이와 창영이가 어떻게 가져가느냐에 따라서 승리자가 바뀔 것 같습니다.
  • 그러나 문제에서 말하는 투는 주어진 N 개의 돌을 어떻게 가져가도 승리자는 정해져있다 라고 말하는 투입니다.
  • 따라서 3 개를 가져가는 경우를 무시하고, 상근이와 창영이가 1 개씩만 가져간다고 생각하고 풀어봤습니다. 어차피 각 N 개 마다 승리자는 정해져있어야 하니까요.
  • 주어진 N 개의 돌을 상근이와 창영이가 1 개씩만 가져간다고 할 때,
    • N = 1 일 때, 상근 승리
    • N = 2 일 때, 창영 승리
    • N = 3 일 때, 상근 승리
    • N = 4 일 때, 창영 승리
    • …
    • 홀수일 때는 상근 승리, 짝수일 때는 창영 승리입니다.
  • 따라서 주어진 N 이 홀수일 때는 “SK” 를 출력, 짝수일 때는 “CY” 를 출력하면 정답이 됩니다.

문제 풀이 step 2

  • 위와 같이 간단하게 풀 수도 있지만, 왜 저렇게 풀릴지 생각해보면 재미있을 것 같습니다.
  • 왜 저렇게 풀릴지는 각 숫자를 1 과 3 으로 구성했을 때, 어떻게 구성되어 있는지 생각해보면 됩니다.
    • N = 1 일 때,
      • 1
    • N = 2 일 때,
      • 1, 1
    • N = 3 일 때,
      • 1, 1, 1
      • 3
    • N = 4 일 때,
      • 1, 1, 1, 1
      • 1, 3
    • N = 5 일 때,
      • 1, 1, 1, 1, 1
      • 1, 1, 3
    • N = 6 일 때,
      • 1, 1, 1, 1, 1, 1
      • 1, 1, 1, 3
      • 3, 3
    • …
  • 두 사람이 완벽하게 게임을 한다는 가정이 있기 때문에 위와 같은 규칙을 확인할 수 있었습니다.
  • N = 6 일 때를 보면, 상근이와 창영이가 돌을 가져가는 경우가 3 개가 나오는데, 3 경우 모두 짝수 턴으로 이루어져 있습니다.
  • 따라서 짝수 턴일 때 돌을 가져가는 창영이가 게임을 이기게 되는 것입니다.
    • 게임은 상근이가 먼저 시작한다는 가정이 있기 때문에 홀수 턴일 때는 상근이가, 짝수 턴일 때는 창영이가 돌을 가져갑니다.
  • 위의 규칙을 일반화해보면,
    • N 이 홀수면 모든 경우는 홀수 턴을 가지고
    • N 이 짝수면 모든 경우는 짝수 턴을 가지게됩니다.
  • 따라서 위와 같은 규칙 때문에, 주어진 N 개의 돌을 어떻게 가져가도 승리자는 정해져있는 것입니다.

후기

  • 알고 보면 상당히 쉬운 문제이지만, 그 속을 알아가는 과정이 너무 재미있어서 포스트하게 되었습니다.
  • 옛날에 수학 문제 풀때 자주 답정너 식으로 문제를 푼적이 많은데, 그런 기분을 오랜만에 다시 느꼈습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	if (Number(input[0]) % 2 === 0) return "CY";
	return "SK";
};

console.log(solution(input));