Yepchani's place

문제계단 오르기https://www.acmicpc.net/problem/2579  풀이설명계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제입니다. 규칙은 다음과 같습니다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있습니다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다다음 계단으로 오를 수 있습니다.연속된 세 개의 계단을 모두 밟아서는 안 됩니다. 단, 시작점은 계단에 포함되지 않습니다.마지막 도착 계단은 반드시 밟아야 합니다. DP를 통해 해결할 수 있습니다. dp[i]는 i번째 계단까지 밟았을 때 얻을 수 있는 최대 점수입니다. 계단에 써있는 점수를 담은 배열을 stairs라고 할 때,dp[i]의 값은 다음 두 가지 중 더 큰 값입니다.dp[i - 2] + stairs..

문제외계인의 기타 연주https://www.acmicpc.net/problem/2841  풀이설명멜로디를 연주하는데 필요한 최소 손가락 움직임을 구하는 문제입니다. 주의해야 할 점은 다음과 같습니다.기타는 1번부터 6번 줄까지 있습니다.어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생합니다.손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 합니다. 스택을 이용해 해결할 수 있습니다. 스택에는 해당 줄에서 누르고 있는 프렛들이 들어있습니다. 멜로디가 입력되면 다음 과정을 수행합니다.멜로디의 줄이 처음 연주됐다면 스택에 프렛을 추가합니다.아니라면 스택에서 멜로디의 프렛보다 높은 프렛은 모두 제거합니다.멜로디의 프렛을 이미 누르고 있지 않다면, 스택에 추가합니다. 예..

문제숨바꼭질https://www.acmicpc.net/problem/1697  풀이설명수빈이가 동생을 찾는 가장 빠른 시간을 구하는 문제입니다. BFS를 이용해 해결할 수 있습니다. 현재 위치를 cx라고 한다면,다음 위치는 cx - 1, cx + 1 또는 2 * cx입니다. 예시 코드function solution() { const [n, k] = input().split(" ").map(Number); if (k LIMIT) continue; if (dist[next]) continue; dist[next] = dist[cx] + 1; queue.enqueue(next); } }}

문제거짓말https://www.acmicpc.net/problem/1043  풀이설명과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 문제입니다. 어느 파티에 진실을 아는 사람이 한 명이라도 있으면, 지민이는 그 파티에서 진실만을 말해야 합니다. Union-Find 알고리즘을 이용해 해결할 수 있습니다. 과정은 다음과 같습니다.같은 파티에 속해 있는 사람들을 같은 그룹으로 묶습니다.진실을 아는 사람들을 같은 그룹으로 묶습니다.어느 파티에 진실을 아는 사람과 같은 그룹에 묶여있는 사람이 있는지 확인하고, 없다면 카운트를 증가시킵니다. 예시 코드function solution() { const [N, M] = input().split(" ").map(Number); const parent = Ar..

문제수들의 합 2https://www.acmicpc.net/problem/2003  풀이설명N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있을 때, 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 문제입니다. 투 포인터 알고리즘을 이용해 풀 수 있습니다. start와 end의 인덱스를 0으로 초기화하고, start부터 end까지의 원소 합과 M을 비교합니다.합이 M보다 크면 start를 증가시키고, M보다 작으면 end를 증가시킵니다. 예시 코드function solution() { const [N, M] = input().split(" ").map(Number); const A = input()...

문제수 이어 쓰기https://www.acmicpc.net/problem/1515  풀이설명1부터 N까지 모든 수를 차례대로 쓰고, 이 중 0개 이상의 숫자를 지우고 남은 수를 이어 붙인 수를 봤을 때, 가능한 N의 최솟값을 구하는 문제입니다. 포인터를 이용해 현재 비교하고 있는 숫자의 위치를 관리합니다.숫자 카운터를 1부터 하나씩 증가시키면서 문자열로 변환해 남은 수와 비교합니다.숫자 문자열을 순회하면서 해당 수가 포인터가 가리키는 수와 일치하면 포인터를 증가시킵니다.남은 수가 없을 때의 숫자 카운터를 반환하면 됩니다. 예시 코드function solution() { const n = input(); let num = 0; let ptr = 0; while (ptr = n.length) brea..

문제상자넣기https://www.acmicpc.net/problem/1965  풀이설명한 줄에 넣을 수 있는 상자의 최대 개수를 구하는 문제입니다. LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)를 구하면 됩니다.다음 두 가지 방법이 있습니다. DP dp[i]는 i번째까지 셌을 때, lis의 길이입니다. dp[i] = Math.max(dp[i], dp[j] + 1); 이분탐색 수열을 순회하면서 원소를 lis의 적합한 위치에 넣어줍니다.두 방법 모두 lis를 이용하므로 접근 방법은 비슷하지만, 실행시간에 차이가 있습니다.DP로 풀 경우, O(N^2)이 걸립니다. 이분탐색으로 풀 경우, O(N logN)이 걸립니다. 예시 코드DPfunction solution() { ..

문제빗물https://www.acmicpc.net/problem/14719  풀이설명고이는 빗물의 총량을 구하는 문제입니다. 두 가지 방법으로 풀어봤습니다. 첫 번째 풀이현재 블록과 이전 위치의 블록 사이에 고이는 빗물 양을 구해 더하는 방식입니다. 스택을 이용합니다.스택에는 블록들의 인덱스와 높이를 저장합니다. 수행 과정은 다음과 같습니다.스택이 비어있지 않은 경우, 다음 과정을 반복해 수행합니다.현재 블록과 마지막 블록 사이에 고이는 빗물 양을 구해 총량에 더합니다.마지막 블록의 높이가 현재 블록보다 작거나 같은 경우, 스택에서 제거합니다.마지막 블록의 높이가 현재 블록보다 크거나 같은 경우, 반복문을 종료합니다.\ 스택에 현재 블록의 인덱스와 높이를 저장합니다. 두 번째 풀이블록 별로 해당 위치에 ..

문제컨베이어 벨트 위의 로봇https://www.acmicpc.net/problem/20055  풀이설명작업이 종료되었을 때 몇 번째 단계가 진행중이었는지를 구하는 문제입니다. 작업 순서는 다음과 같습니다.벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전합니다.가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동합니다. 만약 이동할 수 없다면 가만히 있습니다. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 합니다. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올립니다. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료합니다. 그렇지 않다면 1번으로 돌아갑니다. 예시 코드function so..

문제폴리오미노https://www.acmicpc.net/problem/1343  풀이설명X를 폴리오미노로 모두 덮었을 때, 사전순으로 가장 앞서는 답을 구하는 문제입니다. 폴리오미노의 종류는 두 가지입니다.AAAABB 사전순으로 앞서야 하므로 AAAA를 모두 덮은 다음, 남은 X를 BB로 덮으면 됩니다. 예시 코드function solution() { const S = input(); const result = S.replace(/XXXX/g, "AAAA").replace(/XX/g, "BB"); return result.includes("X") ? -1 : result;}