[99클럽 코테 스터디] 11일차 TIL - 백준 9655 (JS/DP)

[11일차 미들러]

문제: https://www.acmicpc.net/problem/9655

Solution

1 혹은 3 중 어떤 것을 가져도 상관없고, 누군가를 이기도록 설계해야 하는 코드도 아니다. 그래서 더 의아했지만, 문제의 문자 그대로 구현하면 되는 쉬운 그리디 문제라고 생각했다. 이 문제가 그리디에 속하는 이유는, 당장의 최적선택(-1 or -3)을 반복하기 때문. 그러나 -1 또는 -3 중 어떤 것을 선택해도 상관이 없어(결과에 영향x), 최적의 해를 선택했다고 보기 어렵다.

문제 유형을 굳이 따지자면 DP이다. 나는 그렇게 풀지 않았지만, 코드 하단에 간단한 설명을 적어두었다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

const turn = (n) => {
  if (n >= 3) {
    return n - 3;
  } else if (n >= 1) {
    return n - 1;
  } else {
    return n;
  }
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  let n = Number(input[0]);

  let ppl = true;       // ture - SK, false - CY
  let cur = turn(n);    // 게임 1회 진행 후

  while (cur > 0) {
    ppl = !ppl;			// 순서 바뀌고 시작
    if (cur == 0) {	   // cur = 현재 남은 돌 갯수
      return;
    } else if (cur > 0) {
      cur = turn(cur);
    }
  }

  if (ppl == true) {
    console.log("SK");
  } else {
    console.log("CY");
  }
});

ppl = !ppl 과 같이 기존 값을 몰라도 '기존 값의 반대'로 명시하고 싶어서 boolean 값을 사용했다. 시간은 좀 걸렸지만 (168ms) 정답처리 되었다.

 

DP 풀이로 풀 수 있는 문제는 1) 최적 부분 구조 2) 중복이다. 

1) 최적 부분 구조: 각 턴의 최적은 이전 턴들의 최적에 의존한다.

2) 중복: 같은 수의 돌에 대한 상황이 반복 발생할 수 있다. (DP table 활용)

재귀함수로 풀 수도 있지만, DP table을 활용하면 기존 계산 값 저장이 가능하니 훨씬 효율적일 것이다.

 

다음과 같이 문제를 풀 수 있다.

1. DP 테이블 정의하기

• dp[n] = n개의 돌에 대한 게임 과정의 횟수

2. 점화식 찾기

• 각 턴에서는 1개 또는 3개의 돌만 가져갈 수 있다.
• n개의 돌일 때는 n-1개일 때보다 1번 더 동작했을 것이다.
• 그 동작이 곧 1개 혹은 3개를 가져가는 것이므로 점화식은 아래와 같아진다.

dp[n] = min((dp[n-1]+1), (dp[n-3]+1))

3. 초기값 지정

dp[0] = 0
dp[1] = 'SK'
dp[2] = 'CY'

---

그런데 문제를 풀다보면, 돌의 개수(N)이 홀수인 경우 상근이가 이기고, 짝수인 경우 창용이가 이긴다는 것을 발견할 수도 있다. DP 연습용으로 풀이해보기 좋은 문제인 듯 하다.

나다어

나는 다음에 어떻게 풀까

• DP = 최적 부분 구조 + 중복(DP table로 해결)

---

참고:

https://beginnerdeveloper-lit.tistory.com/83

[C++] 백준 9655번 돌 게임