1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제풀이 체스판을 두 개의 체스판으로 나누어 생각하는게 문제의 포인트입니다. 체스판은 하얀색과 검은색, 두 가지 색의 격자로 이루어 져 있습니다. 비숍은 대각선으로만 움직이기 때문에 검은색 자리에선 하얀색 자리에 영향을 줄 수 없기 때문에 나누어 생각하여 시간 복잡도를 현저히 줄일 수 있습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n"); c..
18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 풀이 방법 배양액을 뿌릴 수 있는 케이스를 모두 찾습니다. 케이스를 순회하며 꽃이 피는 개수를 BFS를 통해 구합니다. DFS가 아닌 BFS로 구하는 이유는, 꽃이 핀다면 시간이 지나도 배양액은 흘러가지 않고, 꽃이 핀 자리에서 확산이 멈추기 때문입니다. 따라서 DFS로 구하면 정답을 구할 수 없다고 판단했습니다. 아래 코드 주석을 통해 확인해주세요 let fs = require('fs'); let inp..
9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen문제 풀이 복습차원에서 적습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim() const N = +input; let answer = 0; next(0, Array(N).fill(0)) console.log(answer) function next(row,board) { if(row === N){ answer++ return } for(let i=0; i
풀이 방법 dfs를 통한 백트래킹 문제입니다. 코드는 아래와 같습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n"); const N = +input.shift(); const data = input.map((v) => v.split(" ").map(Number)); const eggsState = data.map((v) => v[0]); let answer = 0; dfs(0, eggsState); console.log(answer); function dfs(index, arr) { //순회를 마치면 탈출 if (index === N) { const count = arr.fil..
1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제풀이 방법 25명중 무작위로 7명을 뽑습니다. 7명중 4명 이상이 ‘이다솜파’라면 dfs함수를 실행합니다. dfs함수는 무작위로 뽑힌 7명이 인접한 자리에 앉아있는지 확인하는 함수입니다. dfs를 활용하여 인접한지 확인할 수 있습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n") .map((v) => v.split("")); let a..
7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 꼭 알아야 하는 개념인 LCS를 활용한 문제입니다. LCS는 2차원 DP로 푸는 경우가 많아서 이 문제를 처음 봤을 때 고민을 많이 했습니다. 복습 차원에서 글을 적습니다. let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n") const N = +input.shift() const dp = Array(N+1).fill(0) let max = 0; fo..