문제 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 N의 최대 길이가 80, 그러나 최소값만 구하면 되기 때문에 백트래킹으로 구현했다. 내부 for문이 1부터 시작하기 때문에 처음 목표 길이에 도달한 값이 최소값이다. 이를 구현하기 위해 flag 변수를 사용했다. 새로운 문자가 만들어질 때마다 좋은수열인지 확인하고 나쁜수열일 경우 다음으로 넘어가지 않는다. str값을 계속 문자열로 유지해야 하는데 처음에는 중간에 숫자로 변경되어 Number의 범위가 초과돼 문제를 틀렸다. 소스 코드 const filePath = ..
문제 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 남극의 모든 단어는 a, c, i, n, t를 포함하고 있어 이 5개의 글자는 반드시 배워야 한다. 따라서 K가 5이하 라면 배울 수 있는 단어는 존재하지 않는다. visited 배열을 통해 현재까지 배운 글자를 체크한다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSync..
문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const board = Array.from({ length: 9 }, () => Array(9)); for (let i = 0; i < 9; i++) { ..
문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 행(idx)를 증가시키며 dfs를 수행한다. 각 행에서는 모든 열(내부 for문)에 대해서 퀸을 놓아본다. 특정 행에서 퀸을 놓을 수 있는 경우가 존재하지 않는 경우 다음 행으로 넘어가지 않고 재귀를 종료한다. 마지막 행까지 도달했다는 것은 모든 행에 퀸을 놓을 수 있다는 것을 의마하기 때문에 answer을 1 증가시킨다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt..
문제 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 풀이 dfs의 인수로 현재의 좌표값을 넣어주는데 이렇게 하면 이중 for문을 사용하지 않아도 된다. 하나의 좌표(x, y)에서 부메랑을 만드는 경우의 수는 5가지로 스킵, (-1, -1), (-1, 1), (1, -1), (1, 1) 이다. 해당 좌표가 이미 사용된 영역이라면 스킵만 수행하고 나머지 경우는 수행하지 않는다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin"..
문제 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const N = +input[0]; const words = []; let result = []; let answer = ""; let visited..
문제 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 능력치의 합의 최대값을 구해야 하기 때문에 선수 11명이 모든 포지션을 선택받을 수 있게 dfs를 수행한다. (idx가 선수 번호) 이미 누군가 배정받은 포지션이거나 해당 선수의 해당 포지션 능력치가 0인 경우 예외 처리를 해준다. 선수 11명이 모두 포지션을 배정받은 경우 최대값을 갱신해준다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = requir..
문제 1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net 풀이 숫자는 반드시 줄어들어야 하기 때문에 arr는 9부터 0까지 역순으로 저장한다. 조합 알고리즘을 사용하여 1자리부터 10자리까지의 줄어드는 수를 모두 구한다. 줄어드는 수를 모두 구한 뒤 저장한 배열을 오름차순 정렬하면 N번 째 수를 쉽게 구할 수 있다. N이 구할 수 있는 숫자의 범위를 초과하는 경우 -1를 출력한다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin"..
문제 14712번: 넴모넴모 (Easy) 네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 www.acmicpc.net 풀이 모든 위치에 넴모를 배치한 경우 그렇지 않은 경우 2가지 탐색을 모두 진행한다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require("fs") .readFileSync(filePath) .toString() .trim() .split("\n"); const [N, M] = input[0].split(" ").map..
문제 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 왼쪽부터 마지막 계란까지 손에 들 계란을 증가시켜야 하기 때문에 재귀를 돌 때마다 idx를 증가시킨다. 재귀 함수 내부 for문에서는 아직 깨지지 않은 계란을 선택해 치는 작업을 수행한다. 재귀를 돌고 복귀할 때 반드시 계란의 내구성을 원상복구 해준다. 소스 코드 const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = require..
