Yepchani's place

문제1로 만들기 2https://www.acmicpc.net/problem/12852  풀이설명정수 X를 1로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다.X가 3으로 나누어 떨어지면, 3으로 나눕니다.X가 2로 나누어 떨어지면, 2로 나눕니다.1을 뺍니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 만드는 데 필요한 연산의 최소 횟수입니다. 점화식은 다음과 같습니다.dp[i]는 다음 세 가지 값 중 최솟값입니다.dp[i - 1] + 1i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1 추가적으로 경로 배열을 하나 만들어, dp 값이 업데이트 될 때마다 경로를 저장합니다.dp..

문제격자상의 경로https://www.acmicpc.net/problem/10164  풀이설명조건을 만족하는 서로 다른 경로의 수를 구하는 문제입니다. 조건은 다음과 같습니다.로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있습니다. (즉, 대각선 방향으로는 이동할 수 없습니다.) 격자에 O로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 합니다.1번 칸과 N × M번 칸은 O 표시가 되어 있지 않습니다.O 표시가 되어 있는 칸은 최대 한 개입니다. DP를 사용해 해결할 수 있습니다. O 표시가 된 칸을 K라고 할 때, 격자에서 갈 수 있는 영역은 K의 우상단과 K의 좌하단입니다.따라서 해당 부분에 대한 경로만 구하면 됩니다. 예시 코드function solution..

문제1로 만들기https://www.acmicpc.net/problem/1463  풀이설명정수 X를 1로 만들기 위해 필요한 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다.X가 3으로 나누어 떨어지면, 3으로 나눕니다. X가 2로 나누어 떨어지면, 2로 나눕니다. 1을 뺍니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 만드는 데 필요한 연산의 최소 횟수입니다. 점화식은 다음과 같습니다.dp[i]는 다음 세 가지 값 중 최솟값입니다.dp[i - 1] + 1i가 2로 나누어 떨어지는 경우, dp[i / 2] + 1i가 3으로 나누어 떨어지는 경우, dp[i / 3] + 1 예시 코드function solution() { const N = +input(); co..

문제체인https://www.acmicpc.net/problem/2785  풀이설명필요한 고리의 최소 개수를 구하는 문제입니다. 방법은 다음과 같습니다.체인을 길이를 기준으로 내림차순으로 정렬합니다.가장 오른쪽 체인(가장 길이가 작은 체인)에서 고리를 하나씩 풀어 가장 왼쪽의 체인 두 개를 연결합니다.모든 체인이 연결될 때까지 2번을 반복합니다. 예시 코드function solution() { const N = Number(input()); const chains = input() .split(" ") .map(Number) .sort((a, b) => b - a); let left = 0, right = N - 1; let answer = 0; while (left

문제수 이어가기https://www.acmicpc.net/problem/2635  풀이설명규칙에 맞춰 만들어지는 최대 개수의 수들을 구하는 문제입니다. 규칙은 다음과 같습니다.첫 번째 수로 양의 정수가 주어집니다. 두 번째 수는 양의 정수 중에서 하나를 선택합니다. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만듭니다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것입니다. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않습니다. 주어진 수를 N이라 할 때,N의 절반에 해당하는 수부터 N까지 1씩 증가시키며 규칙에 맞춰 수열을 만들어 구합니다. 예시 코드function solutio..

문제달팽이https://www.acmicpc.net/problem/1913  풀이설명1부터 N^2까지의 자연수를 달팽이 모양으로 채우고, 주어진 자연수의 위치를 찾는 문제입니다. 방향은 위, 오른쪽, 아래, 왼쪽 순입니다.이동 횟수는 1 -> 1 -> 2 -> 2 -> 3 -> 3 과 같은 식으로 증가합니다.방향 전환 후 이동 횟수만큼 이동하며 수를 채우면 됩니다. 예시 코드function solution() { const N = Number(input()); const target = Number(input()); const maxNum = N * N; const matrix = Array.from({ length: N }, () => Array(N).fill(0)); let num = 1; ..

문제삼각형만들기https://www.acmicpc.net/problem/2622  풀이설명주어진 성냥개비로 만들 수 있는 삼각형의 개수를 구하는 문제입니다. 삼각형을 만들려면 가장 작은 변 2개의 길이의 합이 나머지 변의 길이보다 커야 합니다. 예시 코드function solution() { const N = Number(input()); return countTriangles(N);}function countTriangles(matchsticks) { let totalTriangles = 0; for (let a = 1; a c) totalTriangles++; } } return totalTriangles;}

문제십자카드 문제https://www.acmicpc.net/problem/2659  풀이설명입력된 카드의 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 구하는 문제입니다. 1111부터 시작해서 해당 카드의 시계수까지 카운트를 증가시키며 계산합니다. 예시 코드function solution() { const target = input().split(" ").join(""); const targetClockNum = getClockNum(target); let cnt = 0; for (let i = 1111; i

문제빙고https://www.acmicpc.net/problem/2578  풀이설명사회자가 몇 번째 수를 부른 후에 빙고를 외치게 되는지를 구하는 문제입니다. 일반적인 빙고 규칙을 가집니다.빙고 카운트가 3개가 되어야 "빙고"를 외칠 수 있습니다. 숫자가 불릴 때마다 전체 빙고 개수를 확인하는 대신, 다음과 같은 방법을 사용했습니다.각 숫자의 빙고판 상 위치를 저장합니다.각 행, 열, 대각선별로 채워진 칸 수를 추적합니다.불린 숫자의 위치에 해당하는 행, 열, 대각선만 업데이트합니다. 예시 코드function solution() { const TARGET_BINGO_COUNT = 3; const n = 5; const board = Array.from({ length: n }, () => input..

문제욕심쟁이 판다https://www.acmicpc.net/problem/1937  풀이설명판다가 이동할 수 있는 칸의 수의 최댓값을 구하는 문제입니다. 규칙은 다음과  같습니다.판다의 초기 위치는 어떤 칸이든 될 수 있습니다.상, 하, 좌, 우로 인접한 칸 중 하나로 이동합니다.새로 이동하는 칸은 이전 칸보다 대나무가 많아야 합니다. 그래프 탐색과 DP를 이용해 해결할 수 있습니다. dp[x][y]는 (x, y)에서 시작했을 때, 이동할 수 있는 칸의 수의 최댓값입니다. 다음 칸의 위치를 (nx, ny)라고 할 때, 점화식은 다음과 같습니다.dp[x][y]는 다음 두 값 중 최댓값입니다.dp[x][y]dp[nx][ny] + 1 모든 칸에서 그래프 탐색을 진행하고, 각 칸에 대한 dp 값을 업데이트합니다..