티스토리 뷰

자료구조 알고리즘/백준

Node.js)백준 1285: 동전 뒤집기

LHOIKTN 2022. 4. 1. 00:18

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

 

1285번: 동전 뒤집기

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위

www.acmicpc.net

 

 

2420ms 걸린 게 풀이2

4692ms 걸린 게 풀이1

 

 

 

풀이1:

const { checkPrime } = require('crypto');
const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");


function main(input) {
  const N = +input.shift();
  let board = input.map(v => v.trim().split(''))
  let answer = Infinity;

  const changeRow = (row) => {
    for (let i = 0; i < N; i++) {
      if (board[row][i] == 'T') {
        board[row][i] = 'H'
      } else {
        board[row][i] = 'T'
      }
    }
  }

  const check = () => {
    let cnt = 0;
    for (let i = 0; i < N; i++) {
      let t = 0;
      for (let j = 0; j < N; j++) {
        if (board[j][i] == 'T') {
          t++;
        }
      }
      cnt += Math.min(t, N - t);
    }
    return cnt;
  }


  for (let i = 0; i < (1 << N); i++) {
    for (let j = 0; j < N; j++) {
      if (i & (1 << j)) {
        changeRow(j)
      }
    }

    let res = check()
    if (res < answer) answer = res;

    for (let j = 0; j < N; j++) {
      if (i & (1 << j)) {
        changeRow(j)
      }
    }
  }
  console.log(answer)
}


main(input);

 

 

풀이2:

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




function main2(input) {
  const N = +input.shift();
  let board = input.map(v => v.trim().split(''))
  let answer = Infinity;

  const changeRow = (i) => {
    board[i] ^= (1 << N) - 1;
  }

  board = board.map(v => {
    let num = 0;
    for (let i = 0; i < N; i++) {
      if (v[i] == 'H') {
        num |= (1 << i);
      }
    }
    return num;
  })


  const check = () => {
    let cnt = 0;
    for (let i = 0; i < N; i++) {
      let temp = 0;
      for (let j = 0; j < N; j++) {
        if (board[j] & (1 << i)) {
          temp++;
        }
      }
      cnt += Math.min(temp, N - temp);
    }
    return cnt;
  }


  for (let i = 0; i < (1 << N); i++) {
    for (let j = 0; j < N; j++) {
      if (i & (1 << j)) {
        changeRow(j)
      }
    }

    let res = check()
    if (res < answer) answer = res;

    for (let j = 0; j < N; j++) {
      if (i & (1 << j)) {
        changeRow(j)
      }
    }
  }
  console.log(answer)


}
main2(input);
728x90

'자료구조 알고리즘 > 백준' 카테고리의 다른 글

Node.js)백준 2558번: A+B - 2  (0) 2022.04.01
Node.js) 백준 24078번: 余り (Remainder)  (0) 2022.04.01
Node.js)백준 19942번: 다이어트  (0) 2022.03.31
Node.js)백준 15684번: 사다리 조작  (0) 2022.03.31
Node.js) 백준 9934번: 완전 이진 트리  (0) 2022.03.31
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함