파게로그

문제 링크: 1463번 1로 만들기 https://www.acmicpc.net/problem/1463 예를들어, 9는 '27을 3으로 나눈다'는 한 번의 수행 또는 '10에서 1을 뺀다'는 한 번의 수행을 통해 만들어진다. 이를 통해 점화식을 세우면 다음과 같다. a[n] = min(a[n/3], a[n/2], a[n-1]) + 1 다만 a[n/3]과 a[n/2]는 나누어떨어지지 않는 경우 구할 수 없기에 divBy3, divBy2를 미리 선언하여 i가 3 또는 2로 나누어떨어지지 않을 경우 최댓값을 저장하도록 하여 min()에서 고려되지 않도록 한다. import java.util.Scanner; import java.util.Arrays; class Main { static int[] arr; pub..

문제 링크: 2579번 계단 오르기 https://www.acmicpc.net/problem/2579 s(n) = max( s(n - 2) + a(n), s(n - 3) + a(n - 1) + a(n) )의 식을 이용할 수 있다. 3개 계단을 연속해서 밟으면 안 된다는 조건을 고려해서, s(n -1)을 이용하지 않는 데에 초점을 두는 것이다. C/CPP #include #define MAX(a, b) ((a) > (b) ? (a) : (b)) int n, a[300], d[300]; int main(void) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &(a[i])); d[0] = a[0], d[1] = a[0] + a[1], d[2] = M..

문제 링크: 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 아랫층의 수는 윗층의 수 중 왼쪽 대각선과 오른쪽 대각선의 수만 고를 수 있다. 그리고 이것이 배열로 들어올 때는 아랫층 수가 a[row][col]이라면 왼쪽 대각선의 수는 a[row][col-1], 오른쪽 대각선의 수는 a[row][col]이다. 위에서부터 아래로 내려오면서, 윗층의 수 중 큰 것과 아랫층의 수를 더해서 저장하면 된다. 구현을 편리하게 하기 위해 triangle의 폭을 n+2로 선언하고 값을 입력받기 전 triangle을 -1(또는 0)로 초기화해두면 반드시 triangle 내의 숫자만 고려되기 때문에 왼쪽 끝과 오른쪽 끝을 신경쓸 필요가 없다. C/CPP #include #define..

문제 링크: 1149번 RGB거리 https://www.acmicpc.net/problem/1149 DP 문제이다. 연속된 집은 같은 색깔로 칠할 수 없으므로, i번째 집까지의 최솟값 mem[i] 중에서도 i번째 집이 RED일 때의 최솟값 mem[i][RED]는, i-1번째 집까지의 최솟값 mem[i-1] 중에서도 i-1번째 집이 GREEN일 때의 최솟값(mem[i][GREEN])과 i-1번째 집이 BLUE일 때의 최솟값(mem[i][BLUE])에 i번째 집을 RED로 칠할 때의 비용(arr[i])을 더한 것이다. 이처럼 mem[i]는 i번째 집의 색깔에 따라 세 개의 값을 저장하고 있어야 한다. import java.util.Scanner; public class Main { static int RED..

문제 링크: 9461번 파도반 수열 https://www.acmicpc.net/problem/9461 나열을 통해 다음과 같은 점화식을 이끌어낼 수 있다. a[n] = a[n-1] + a[n-5] 참고로, 이는 정삼각형의 한 각의 크기가 60도라는 것과 관련이 있다고 한다. 그리고 처음에 long형을 사용하지 않아서 틀렸다. 생각보다 숫자가 빨리 커지는데, 대략적인 숫자의 크기에 대해서도 충분히 고려해야 할 것이다. import java.util.Scanner; public class Main { public static long longest(int n) { long[] arr = new long[101]; arr[1] = 1; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5..

문제 링크: 1904번 제목 https://www.acmicpc.net/problem/1904 n은 길이이므로, 1자리가 더 길면 a[n-1]의 원소마다 '1'을 붙일 수 있고, 2자리가 더 길면 a[n-2]의 원소마다 '00'을 붙일 수 있다. a[n-2]에서는 '1'을 붙이는 것을 고려할 필요가 없는데, a[n-1]의 원소에 '1'을 붙인 것과 중복되는 결과이기 때문이다. 따라서 a[n]을 '00'과 '1' 타일로 만들 수 있는 2진 수열의 개수라고 할 때, 점화식은 다음과 같다. a[n] = a[n-1] + a[n-2] 다만 숫자가 굉장히 크니 문제에서 제시된 15746으로 계속해서 나누어주면서 계산하는 편이 좋다. import java.util.Scanner; public class Main { ..

문제 링크: 2580번 제목 https://www.acmicpc.net/problem/2580 1. 스도쿠 판을 입력받으면서 빈 칸을 별도의 목록 empty에 저장한다. 2. empty의 각 칸에 대해서 2-1. 가능한 숫자의 목록을 구한다. 2-2. 해당 숫자를 집어넣고, 그 다음 칸으로 넘어간다. 2-3-1. 마지막 칸이 아님에도 가능한 숫자가 없다면, 되돌아간다. 2-3-2. 마지막 칸이고 가능한 숫자가 있다면, 첫 숫자를 넣고 종료한다. 되돌아갈 때, 반드시 집어 넣을 숫자를 삭제하여, 즉 다시 0으로 만들어주어 되돌아간 빈 칸에서 '가능한 숫자'가 '불가능한 숫자'가 되지 않도록 주의한다. import java.util.Scanner; import java.util.ArrayList; impor..

문제 링크: 프로그래머스 Lv.2 주식가격 https://programmers.co.kr/learn/courses/30/lessons/42584 인덱스 curIdx를 통해 주식 가격 리스트를 읽어나가면서, 스택에 현재 가격과 인덱스를 묶어서 push한다. 그러다가 현재 가격이 스택 맨 위의 가격보다 같거나 낮으면, 이는 주식 가격이 떨어졌다는 것을 의미하므로, 스택의 원소들을 pop한다. 현재 시점(curIdx)과 기록된 시점(topIdx)의 차이가 곧 '가격이 떨어지지 않은 기간'이며, pop한 원소의 인덱스야말로 우리가 구하는 answer의 인덱스이기에, answer[Idx] = curIdx - topIdx를 실행한다. 그러다가 스택 맨 위의 가격이 현재 가격보다 같거나 낮으면, 현재 가격은 더 이상..