빌런 호석 (백준 22251)

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

22251번: 빌런 호석

 

재미있는 문제였다. 물론 구현에는 실패했지만. 문제를 분석해보자.

 

N : 1부터 N층까지 이용 가능

K : 디스플레이는 K자리 수

P : LED의 반전 갯수는 최소 1개 ~ 최대 P개

X : 현재 엘리베이터가 멈춘 층은 X층

 

우선 이렇게 디스플레이의 숫자를 배열로 표현할 수 있겠다.

  const ch = [

    [1, 1, 1, 0, 1, 1, 1], // 0

    [0, 0, 1, 0, 0, 0, 1], // 1

    [0, 1, 1, 1, 1, 1, 0], // 2

    [0, 1, 1, 1, 0, 1, 1], // 3

    [1, 0, 1, 1, 0, 0, 1], // 4

    [1, 1, 0, 1, 0, 1, 1], // 5

    [1, 1, 0, 1, 1, 1, 1], // 6

    [0, 1, 1, 0, 0, 0, 1], // 7

    [1, 1, 1, 1, 1, 1, 1], // 8

    [1, 1, 1, 1, 0, 1, 1], // 9

  ];

 

여기까지는 생각을 할 수 있었다.

구현이 막혔던 부분은 만약 X가 35이고 P가 5라면 앞에 3을 3번 바꾸고 5를 2번 바꿔야하는지 3을 4번 바꾸고 5를 1번 바꿔야되는지 이 부분이 헷갈리고 어떻게 구현해야할지 감이 오지 않았다.

 

다음 과정을 이어서 생각해보자.

우리가 만들 수 있는 숫자의 범위는 1부터 N까지이다. 그렇기 때문에 1부터 N까지 for문을 돌리면서 현재 위치한 x에서 i를 만들 수 있는지 확인해야한다.

let cnt = 0;

    let from = x;

    let to = i;

    for (let j = 0; j < k; j++) {

      for (let z = 0; z < 7; z++) {

        if (ch[from % 10][z] !== ch[to % 10][z]) cnt++;

      }

      from = Math.floor(from / 10);

      to = Math.floor(to / 10);

    }

    if (cnt <= p) res++;

 

이 코드 부분이 핵심이다. 

숫자를 하나씩 분리해서 LED의 갯수가 몇개가 다른지 카운팅한다. 이 갯수가 결국 반전해야하는 갯수랑 같기 때문이다.

그리고 최대 p번까지 반전을 할 수 있으므로 cnt가 p보다 작거나 같다면 결과값을 카운팅해주면 된다.

🛠코드

아이디어, 또 아이디어, 그리고 다시 아이디어...

function solution() {
  let [n, k, p, x] = require('fs').readFileSync(0).toString().trim().split(' ').map(Number);

  const ch = [
    [1, 1, 1, 0, 1, 1, 1], // 0
    [0, 0, 1, 0, 0, 0, 1], // 1
    [0, 1, 1, 1, 1, 1, 0], // 2
    [0, 1, 1, 1, 0, 1, 1], // 3
    [1, 0, 1, 1, 0, 0, 1], // 4
    [1, 1, 0, 1, 0, 1, 1], // 5
    [1, 1, 0, 1, 1, 1, 1], // 6
    [0, 1, 1, 0, 0, 0, 1], // 7
    [1, 1, 1, 1, 1, 1, 1], // 8
    [1, 1, 1, 1, 0, 1, 1], // 9
  ];
  // 디스플레이는 k개 보여지고, p개까지만 바꿀 수 있으며 현재는 x층이다.
  let res = 0;
  for (let i = 1; i <= n; i++) {
    // 만약 i가 현재 층 x와 같을 경우에는 판단할 필요가 없다.
    if (i === x) continue;
    // i층을 표현하기 위해 바꾼 디스플레이의 갯수
    let cnt = 0;
    let from = x;
    let to = i;
    for (let j = 0; j < k; j++) {
      for (let z = 0; z < 7; z++) {
        if (ch[from % 10][z] !== ch[to % 10][z]) cnt++;
      }
      from = Math.floor(from / 10);
      to = Math.floor(to / 10);
    }
    if (cnt <= p) res++;
  }
  return res;
}

console.log(solution());