프로그래머스 | 필승법 반대의 함수 구하기

📌 문제

플레이어 A와 B가 게임을 합니다.
N개의 블럭이 있을 때, A와 B는 1개 혹은 2개 혹은 3개의 블럭을 한 번에 가져갈 수 있습니다.
게임은 플레이어의 차례에 1개가 남으면 패배합니다.
N은 0 초과 1000 이하입니다.

플레이어 A가 무조건 먼저 시작하고 A와 B가 모두 필승법을 안다고 가정했을 때, 블럭 개수 N개로 시작하여 플레이어 A가 승리할 수 있는 지의 여부를 boolean으로 출력하세요.

✨ 해결 방법

우선 필승법이 무엇인지 알아야 합니다.
필승법이란 베스킨라빈스 31 게임의 공략법으로 잘 알려져 있습니다.

사용자는 2, 6, 10, 14, 18, 22, 26, 30의 숫자를 본인 차례에서 말할 경우 승리하게 됩니다.
플레이어 A가 마지막 숫자 30을 본인 차례에서 말해야 반대의 타자가 31을 말할 수 밖에 없겠죠.

우리의 프로그램은 이 필승법과 반대의 방향으로 작동합니다.

1  | 2  3  4
5  | 6  7  8
9  | 10 11 12
13 | 14 15 16
....

본인의 앞에서 5개가 남을 경우 최대 3개를 가져가도 상대에게는 2개 이상이 남게 되어 지게 됩니다. 이는 가져갈 수 있는 최대 개수인 3개를 단위로 반복되는 현상을 보입니다.

따라서 플레이어 A 차례에서 1, 5, 9, 13...개가 있다면 패배한다는 것을 의미하며, 그 말은 즉슨 플레이어 B 차례에서 1, 5, 9, 13...의 갯수가 남아야지만 승리할 수 있습니다.

이는 공차(d)가 4인 등차수열을 구하는 것과 같습니다.
0번째는 1 + 4 * 0, 1번째는 1 + 4 * 1, 2번째는 1 + 4 * 2... 이기 때문에 n항은 1 + 4 * n이고, 각 변에 -1을 더하면 n - 1 = 4n, 즉 n = (n - 1) / 4 라는 값이 도출됩니다.

그렇다면, 필승법에 부합하는 n항의 공통점은 4로 나누어 떨어진다는 것이겠지요. 따라서 나머지 % 연산자를 사용하여 공식을 유도할 수 있습니다.

💻 solution

function solution(num) {
    if(0 < num && num <= 10000){
        if((num - 1) % 4 == 0){
        return false;
    } else {
        return true;
    }
    } else {
        console.log("범위에서 벗어났습니다.");
    }
}

결론적으로, 필승법에 부합하는 n항일 경우 플레이어 A는 무조건 패배하며, 나머지의 경우는 승리할 가능성이 있다는 것을 판단할 수 있습니다.

위 식을 아래처럼 더 줄일 수 있다.
return의 기본 값은 undefined기 때문에 0이 나온다. 따라서 true인 경우만 도출한다.
또한 num - 1이 4로 나누어 떨어지는 것은, num을 4로 나누었을 때 나머지가 1이 나오는 것과 같다.

function solution(num) {
    return num % 4 != 1;
}