문제 링크 https://www.acmicpc.net/problem/23328 23328번: 마을 구하기 미소가 사는 마을에는 $N$채의 집이 일렬로 있다. 어느 날 밤, 마을 내 모두가 잠든 사이에 집마다 폭탄 혹은 폭탄 쉴드가 배치되었다. 폭탄과 폭탄 쉴드는 다음과 같은 특징이 있다. 폭탄은 알파 www.acmicpc.net 풀이 몇 번 끄적여보며 잘 관찰하면, '사전순으로 가장 앞서는 배치'라는 조건 때문에 폭탄을 연속으로 배치해야 한다는 사실을 알 수 있습니다. 예를 들면 다음처럼요. 'bBBbb' < 'bBbBb' 위 사실을 전제로 폭탄을 배치해 봅시다. 확정적인 케이스부터 처리해 나가면 어렵지 않습니다. 터지는 폭탄을 bomb, 그에 맞는 쉴드를 shield, 터지지 않는 폭탄을 upper, ..
문제 링크 https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 개요 문제가 복잡합니다. 과정별로 반복되는 행동을 정리해서 구현합시다. 기본적으로 어항들을 이차원 배열로 관리합니다. 함수형 패러다임을 이용하면 과정별로 함수를 만들어 잘 조립해주기만 하면 됩니다. 1. 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 이를 addFish() 함수에서 구현합니다. 2. 어항을 규칙에 따라 쌓는다. 설명이 복잡하지만 어항을 돌돌 말아버린다고..
문제 링크 https://www.acmicpc.net/problem/25289 25289번: 가장 긴 등차 부분 수열 길이가 $N$인 수열 $A$가 주어진다. $A$의 부분 수열 중, 등차 수열인 가장 긴 부분 수열의 길이를 출력하는 프로그램을 작성하자. 부분 수열과 등차 수열이 무엇인지 잘 모르는 친구들은 친절한 준 www.acmicpc.net 풀이 등차수열의 공차가 고정되었다고 생각하면 정말 간단한 dp 문제가 됩니다. $d[\text{num}]$: 공차 $\text{diff}$에 대해, $\text{num}$이 끝 부분에 위치하는 등차수열의 최대 길이. $d[\text{num}] = d[\text{num} - \text{diff}] + 1$ 원소의 범위가 1 ~ 100이기 때문에 공차의 범위는 -9..
문제 링크 https://www.acmicpc.net/problem/25288 25288번: 영어 시험 aa(abba), ab(abba), ba(abba), bb(abba) 를 모두 부분 수열로 갖는다. www.acmicpc.net 풀이 주어진 알파벳과 자릿수가 주어졌을 때, 중복 순열의 모든 케이스가 답이 될 수 있습니다. 각 자리에 어떤 알파벳이든 올 수 있어야 하므로 자리마다 모든 알파벳을 배치해줍시다. 예를 들어 길이가 4, 알파벳이 abc인 경우, abc / abc / abc / abc처럼 구성하면 가능한 모든 케이스를 고려할 수 있습니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require('fs'); cons..
문제 링크 https://www.acmicpc.net/problem/25287 25287번: 순열 정렬 $1$부터 $N$까지의 정수를 임의로 배열한 순열은 총 $N! = N\times(N-1)\times(N-2)\times\cdots\times1$가지가 있다. 예를 들어 $1$부터 $3$까지의 수를 임의로 배열한 순열은 $\lbrace1,2,3\rbrace, \lbrace1,3,2\rbrace, \lbra www.acmicpc.net 풀이 앞에서부터 탐색하며 각 자리의 수를 결정합니다. $i$와 $N-i+1$ 중, 앞자리의 수보다 크면서, 더 작은 수를 선택하면 됩니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require..