Yepchani's place

문제폴리오미노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;}

문제단어 뒤집기 2https://www.acmicpc.net/problem/17413  풀이설명주어진 문자열을 뒤집은 결과를 구하는 문제입니다. 규칙은 다음과 같습니다.알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있습니다.문자열의 시작과 끝은 공백이 아닙니다.''가 문자열에 있는 경우 번갈아가면서 등장하며, ' 문자열을 순회하면서 태그 여부와 공백인지에 따라서 값을 처리하면 됩니다.태그가 시작된 후의 문자들은 전부 배열에 넣고, 태그가 끝나면 뒤집어서 정답 배열에 넣어줍니다.태그 바깥의 문자들은 전부 배열에 넣고, 공백 또는 태그를 마주치면 뒤집어서 정답 배열에 넣어줍니다. 예시 코드function solution() { const S = inp..

문제RGB거리 2https://www.acmicpc.net/problem/17404  풀이설명모든 집을 칠하는 비용의 최솟값을 구하는 문제입니다.규칙은 다음과 같습니다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 합니다. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 합니다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 합니다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 합니다. RGB거리 문제에서 규칙만 조금 바뀌었습니다. 첫 번째 집에서 고른 색은 마지막 집에서 고를 수 없습니다.DP를 이용해 해결할 수 있습니다. dp[i][j]는 i번째 집까지 색칠을 마쳤고, i번째 집을 j색으로 칠했을 때의 비용의 최솟값입니다. i번째 집을 j색으로 칠..

문제RGB거리https://www.acmicpc.net/problem/1149  풀이설명모든 집을 칠하는 비용의 최솟값을 구하는 문제입니다. 규칙은 다음과 같습니다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 합니다.1번 집의 색은 2번 집의 색과 같지 않아야 합니다.N번 집의 색은 N-1번 집의 색과 같지 않아야 합니다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 합니다. DP를 이용해 해결할 수 있습니다. dp[i][j]는 i번째 집까지 색칠을 마쳤고, i번째 집을 j색으로 칠했을 때의 비용의 최솟값입니다. i번째 집을 j색으로 칠했을 때의 최솟값은 (i - 1번째 집을 j가 아닌 색으로 칠했을 때의 최솟값) + (i번째 집을 j색으로 칠했을 때의 최솟값)입..

문제지름길https://www.acmicpc.net/problem/1446  풀이설명운전해야 하는 거리의 최솟값을 구하는 문제입니다. DP를 이용해 해결할 수 있습니다. dp[i]는 i 지점까지 운전해야 하는 거리의 최솟값입니다.dp[0] = 0으로 초기화합니다. 점화식은 다음과 같습니다.고속도로를 따라 이동할 경우dp[i] = Math.min(dp[i], dp[i-1] + 1)지름길로 이동할 경우도착 지점이 end, 길이를 dist라고 할 때dp[end] = Math.min(dp[end], dp[i] + dist) 예시 코드function solution() { const [N, D] = input().split(" ").map(Number); const dp = Array(D + 1).fill(D..

문제2 x n 타일링 2https://www.acmicpc.net/problem/11727   풀이설명직사각형을 채우는 방법의 수를 구하는 문제입니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i칸까지 타일을 채울 수 있는 방법의 수입니다.dp = [0, 1, 3]으로 초기화해줍니다. 타일을 채울 수 있는 방법의 수는 다음과 같습니다.2x1 타일을 놓는 경우, 남은 부분은 2x(n-1)이므로 dp[n-1]가지입니다.1x2 타일을 놓는 경우, 남은 부분은 2x(n-2)이므로 dp[n-2]가지입니다.2x2 타일을 놓는 경우, 남은 부분은 2x(n-2)이므로 dp[n-2]가지입니다. 이를 점화식으로 나타내면 다음과 같습니다.dp[i] = dp[i - 1] + 2 * dp[i - 2] 예시 코드funct..

문제오셀로 재배치https://www.acmicpc.net/problem/13413  풀이설명로봇을 이용해 작업을 진행했을 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 문제입니다. 로봇은 다음 두 가지 작업 중 하나를 골라 진행할 수 있습니다.배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꿉니다.말 1개를 들어 뒤집아 넣이 색상을 변경합니다. 횟수를 최소화하기 위해서는 1번 작업을 최대한 진행 후, 2번 작업을 진행해야 합니다.색이 다른 돌 개수를 각각 센 후, 둘 중 더 큰 값을 반환하면 됩니다. 예시 코드function solution() { const T = +input(); const answer = []; for (let i = 0; i

문제다각형 그리기https://www.acmicpc.net/problem/2641  풀이설명표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열들을 모두 구하는 문제입니다. 다음 과정을 통해 표본 모양수열과 같은지를 구합니다.모양수열의 시작 인덱스를 (0, 0)으로 잡고 그립니다. 각 점의 좌표를 모두 구합니다.정규화를 진행합니다. 좌표를 x, y가 작은 것부터 오름차순으로 정렬합니다. 이중 첫 번째 좌표를 원점으로 잡고, 모든 좌표에서 원점의 좌표만큼 빼주어 재배치시킵니다.표본 모양수열과 해당 모양수열의 모든 좌표가 같은지를 비교합니다. 예시 코드function solution() { const length = Number(input()); const sampleSequence = input().s..

문제줄 세우기https://www.acmicpc.net/problem/2631  풀이설명아이들을 번호 순서대로 줄을 세울 때, 움직여야 하는 아이의 최소 수를 구하는 문제입니다. LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)를 구하면 됩니다.lis를 구한 후, 전체 수에서 lis의 길이를 빼면 움직여야 하는 아이의 최소 수가 됩니다. 다음 두 가지 방법이 있습니다.DPdp[i]는 i번째까지 셌을 때, lis의 길이입니다.dp[i] = Math.max(dp[i], dp[j] + 1);이분탐색수열을 순회하면서 원소를 lis의 적합한 위치에 넣어줍니다. 두 방법 모두 lis를 이용하므로 접근 방법은 비슷하지만, 실행시간에 차이가 있습니다.DP로 풀 경우, O(N^2)이..

문제동전https://www.acmicpc.net/problem/9084  풀이설명동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 구하는 문제입니다. DP를 이용해 해결할 수 있습니다. dp[i]는 금액 i를 만들 수 있는 방법의 수입니다.동전 종류와 개수만 가지고 방법을 세므로 누적합을 이용할 수 있습니다.dp[0] = 1로 초기화 해줍니다. 동전 종류가 coin이라고 한다면, i원을 만들 수 있는 방법의 수는 다음과 같습니다.이전까지의 동전 종류로 민들 수 있는 방법의 수 + (i - coin)원을 만들 수 있는 방법의 수입니다.따라서 dp[i] = dp[i] + dp[i - coin]입니다. 예시 코드function solution() { const T = Number(input())..