명왕성의 공전기록

https://www.acmicpc.net/problem/1149 문제를 간단히하면 옆에 있는 집과 색이 같지 않게끔 하면서 색을 칠했을 때의 최소비용을 구하는 문제다. 이 문제는 다이나믹 프로그래밍을 통해 해결할 수 있는데, 아래 표로 이해를 도우려한다. 먼저 위의 예제를 빌려, 1번째 집이 각각의 색으로 색칠할 때의 비용과 2번째 집을 붉은 색으로 칠할 때의 비용만 주어진다고 가정하자. Red Green Blue 1 26 40 83 2 49 (채택) - - 이때의 2번집을 붉은 색으로 칠할 때의 최소비용은 89이 된다. (옆집과 같은 색은 사용할 수 없고, 남은 녹색과 푸른색 중 더 값싼 녹색을 선택해야 하기 때문.) Red Green Blue 1 - (동일한 색 선택 불가) 40 (최솟값) 83 2..

https://www.acmicpc.net/problem/14501 문제는 '퇴사 전'까지 가장 많은 수익을 얻는 경우의 수익을 구하는 문제다. 상담마다 필요한 '기간'이 주어지기 때문에 모든 상담을 진행할 수 없는데, 이 때 모든 경우의 수를 직접 구할 수 없으므로 DP를 통해 해결한다. 위 문제에서 주어진 예시로 설명을 하자면, 접근 방식은 다음과 같다. 1일차에 상담을 진행했다고 한다면(소요기간 3일 / 수익 10), 소요기간이 3일이기 때문에 2-3일은 다른 사람과의 상담이 불가능하고, 나머지 일자에는 1일차에 상담을 진행한 경우의 아래와 같이 수익을 남게 한다. (4,5,6,7일차에 상담을 한다면, 1일차의 수익까지 가져갈 수 있기 때문) 1일 2일 3일 4일 5일 6일 7일 10 0(상담 X)..

https://www.acmicpc.net/problem/1158 해당 문제는 특정 번째 사람을 제거하는 식으로 진행되므로, 선입선출 방식을 적용할 수 있는 queue 자료 구조로 문제를 해결하면 된다. 이 문제의 풀이는 배열로 queue를 구현하여 적용했다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim() function solution(data) { const [N,K] = data.split(' ').map(Number) const queue = Array.from({length : N}, (_,idx)=> idx + 1..

https://www.acmicpc.net/problem/2292 해당 문제는 반복문을 통해 문제를 해결하려고 하면 시간 초과가 나게 되므로 규칙성을 찾아 해결해야 한다. 중심을 시작으로 각 거리마다 가장 큰 값이 [1, 7, 19, 37, 61]인 것을 보아, 6n[6, 12, 18, 24...]씩 증가하고 있음을 확인할 수 있으므로 이를 활용해 문제를 해결하면 된다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim() function solution(data) { // sum 의 초깃값이 1인 이유는, 벌집 가장 가운데 있는 ..

https://www.acmicpc.net/problem/9324 해당 문제는 주어진 텍스트가 조건에 맞는지 판별하는 문제다. 문제 설명이 조금 미흡한데, '각 문자가 세 번째 등장할 때'가 아니라 '각 문자가 3의 배수로 등장할 때마다'를 적용하고 풀어야 문제가 해결된다. 문제를 해결한 방식은 다음과 같다. 예제로 주어진 문자열인 'AABA'를 예시를 들면, 조건에 맞게끔 'AABAA'를 만든 뒤 비교해주고 두 문자열이 일치하면 OK, 그렇지 않을 시 FAKE를 반환하도록 했다. 이는 구현이 간단한 편인데, 먼저 각 문자가 등장한 횟수를 담을 객체, 비교를 위한 문자열 변수를 하나 선언한다. 이후 각 문자가 등장할 때마다 해당 객체에 추가한다. 반복문을 진행하며 만약 해당 문자열 등장 횟수가 3의 배수..

https://www.acmicpc.net/problem/1063 문제는 체스판에서 말을 움직이는 문제로, 비교적 자주 볼 수 있는 문제다. 조금 다른 점은 이 문제는 '말' 뿐만 아니라, '돌'도 주어지는데, 이 '돌'은 '말'이 미는 방향으로 움직일 뿐더러 이 또한 좌표 밖으로 벗어나서는 안된다는 제약이 주어진다. 나는 다음과 같이 문제 풀이 방식을 수립했다. 1. 먼저 처음 '말'과 '돌'의 위치로 주어지는 좌표가 'A8'와 같은 체스 좌표로 주어지기 때문에, 해당 체스 좌표를 x,y 좌표로 || x,y 좌표를 체스 좌표로 바꿀 수 있는 함수(정답 제출 시 필요)를 구현하고 2. '말'과 '돌'이 명령어에 따라 이동하는 좌표가 유효한 위치인지 확인할 수 있는 함수 구현, 3. 각 명령어에 따라 좌표..

https://www.acmicpc.net/problem/3107 해당 문제는 문제에서 주어진 규칙대로 구현하는 문제다. 1번 규칙을 해결하기 위해서 생략된 0을 채워줄 함수를 하나 만들었고 2번 규칙은 쌍 클론(::)이 사용되어 생략된 내용이 있는 경우와 그렇지 않은 경우에 따로 접근해 해결했다. 소스 코드는 다음과 같다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim() // 0이 생략된 문자열에 0을 채워주는 함수 const padStartAct = (arr) => { return arr.map((el)=> { return..

https://www.acmicpc.net/problem/3036 문제는 다음과 같이 이어진 링이 있다고 할 때, 첫 번째 링을 돌릴 시 다음 링이 몇 바퀴 도는지 출력하는 문제다. 먼저 수학적인 접근을 해본다. 예제 1과 같은 예시로 8, 4, 2의 링이 있다고 할 때, 첫 번째 반지름 8인 링의 둘레는 16π 이다. (모든 링이 16π를 만족할 만큼 회전해야 한다는 의미기도 하다.) 이때 반지름 4인 링의 둘레는 8π 로 2바퀴(2/1)가, 반지름 2인 링의 경우 4π로 4바퀴(4/1)가 답이 된다. (밑에서는 둘레를 구한 뒤 계산하지는 않는다.) 사실 해당 문제에서 가장 중요한 포인트는 '기약분수' 형태로 답안을 제출하는 것인데, 우리는 중학교 때 배웠던 것처럼 최대공약수를 구한 뒤, 분자와 분모..