데구리 블로그

문제 링크 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..

문제 링크 https://www.acmicpc.net/problem/25286 25286번: 11월 11일 11월 11일에는 농업인의 날, 가래떡 데이, 보행자의 날, 대한민국 해군 창설 기념일, 유엔참전용사 추모의 날, 빼빼로 데이 등 다양한 의미를 가진 날이다. 성현이는 11월 11일의 11일 전은 10월 31일, www.acmicpc.net 풀이 JS는 Date 객체를 이용하면 간단하게 풀 수 있습니다. 다만 Date 객체는 기본적으로 로컬 타임에 맞춰버리니 UTC라고 명시해줘야 편합니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require('fs'); const stdin = fs.readFileSync('/dev..

문제 링크 https://www.acmicpc.net/problem/25285 25285번: 심준의 병역판정검사 병역판정검사는 병역의무자들의 상태를 검사해 징병 여부와 징병 시 어느 방향으로 복무를 시키는 게 좋을지 판정하는 검사로, 남성들은 만 19세가 되는 해에 모두 병역판정검사를 받는다. 신체 www.acmicpc.net 풀이 여러 개의 조건문을 이용하여 풀어주면 됩니다. 저 같은 경우는 명확히 키만으로 급수가 나오는 경우를 classifyWithHeight() 함수로, 그 외의 경우를 classifyWithBMI() 함수로 빼서 판단했습니다. 정답 코드 // @BOJ ------------------------------------------ const fs = require('fs'); cons..

문제 링크 https://www.acmicpc.net/problem/22983 22983번: 조각 체스판 높이 $N$, 너비 $M$의 정사각형 격자에 검은색과 흰색 중 한 가지 색이 칠해져 있다. 머릿속이 체스로 가득찬 현채는 문득 이 격자를 잘랐을 때 체스판이 되는 경우가 몇 가지인지 궁금해졌다. 체 www.acmicpc.net 풀이 유사한 문제로 가장 큰 정사각형을 찾는 문제가 있습니다. (BOJ 1915 - 가장 큰 정사각형) 여기에 더해서 체스판이 될 수 있는 정사각형의 개수를 구해야 합니다. 잘 생각해보면, $(i, j)$번 칸을 기준으로 새로운 체스판을 만들었을 때 추가되는 체스판의 개수는 그 칸을 끝점으로 하는 모든 체스판의 개수와 동일합니다. $(i, j)$칸을 끝점으로 하는 가장 큰 체스..

문제 링크 https://www.acmicpc.net/problem/22991 22991번: 수요응답형 버스 현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호 www.acmicpc.net 풀이 버스의 최대 배정 배차 요청에 탑승 인원, 대기 가능시간이, 버스에 정원과 도착 예정 시간이 있습니다. 어떤 배차 요청에 버스가 배정되려면 (탑승 인원 $\leq$ 버스 정원), (대기 가능 시간 $\geq$ 도착 예정 시간)을 만족해야 합니다. 인원을 $x$축으로, 시간을 $y$축으로 두고 그래프를 그려봅시다. 검은 점은 배차 요청을, 빨간 x는 버스를 나타냅니다...

문제 링크 https://www.acmicpc.net/problem/4828 4828번: XML 인터넷프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 항상 학생들에게 XML의 장점을 어필한다. 그러나 잘못 사용되었다가는 지구를 파괴할 수도 있는 무시무시 www.acmicpc.net 풀이 죽여..줘... 정답 코드 const fs = require('fs'); const stdin = fs.readFileSync('/dev/stdin').toString().split('\n'); const input = (() => { let line = 0; return () => stdin[line++]; })(); const main = function () { let s, ans = ..