da9dac

문제

접근 방식

문제 자체는 간단한데 어떻게 풀어야 할지 어려웠던 문제였지만

일단 규칙을 찾아야 할 거 같아서 수들을 적다 보니 특징을 발견해서 풀 수 있었다.

1	10	101
2	12	121 123
3	21	210 212
4	23	232 234
5	32	
6	34
7	43
8	45
9	54	(생략)
	56
	65
	67
	76
	78	787 789
	87	876 878
	89	898
	98	987 989

각각 한 자리부터 세 자리까지의 쉬운 계단 수를 나열한 목록인데

0과 9로 끝나는 부분만 제외한 모든 수들이 2배씩 늘어나고

0과 9로 끝나는 경우만 그대로 하나인 것을 알 수 있다.

0으로 끝나는 경우에는 09가 될 수 없으니 01만 올 수 있고

9로 끝나는 경우도 마찬가지로 90이 될 수 없으니 98만 올 수 있다.

0과 9를 제외한 1~8로 끝나는 수들은 전부 자기 자신 - 1, 자기 자신 + 1

이렇게 두 가지로 늘어날 수 있기 때문에 이 특징들을 이용해 계산해 주면 된다.

우선 DP 테이블은 각 자릿수별로 특정 숫자로 끝나는 가짓수를 기록하기 위해

다음과 같이 2차원 배열로 정의했다.

dp[n][10] = 1 ~ n번째 자리수의 0 ~ 9로 끝나는 경우의 수

이제 위에서 정리한 쉬운 계단 수의 특징들을 가지고 테이블을 채워주면 되는데

0과 9의 경우는 기존 가짓수를 그대로 따라가기 때문에

d[i][0] = d[i-1][1]
d[i][9] = d[i-1][8]

위와 같이 이전 값을 그대로 기록해주면 된다.

각각 이전 자리수의 0번과 9번 값을 가져오지 않고 1번과 8번을 가져오는 이유는

이전 자리수가 1인 경우에만 10처럼 0으로 끝날 수 있고

이전 자리수가 8인 경우에만 89처럼 9로 끝날 수 있기 때문이다.

d[i][j] = d[i-1][j-1] + d[i-1][j+1]

2 ~ 8의 경우에는 이전 자릿수의 j-1과 j+1인 경우에 j가 될 수 있으니

두 값을 모두 더해주면 된다.

풀이

public class Main {

	private static final int MOD = 1_000_000_000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		byte n = Byte.parseByte(br.readLine());

		long[][] dp = new long[n + 1][10];

		dp[1] = new long[]{0, 1, 1, 1, 1, 1, 1, 1, 1, 1};

		for (byte i = 2; i <= n; i++) {
			dp[i][0] = dp[i - 1][1] % MOD;
			dp[i][9] = dp[i - 1][8] % MOD;
			for (byte j = 1; j < 9; j++) {
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
			}
		}

		long count = 0;

		for (byte i = 0; i < 10; i++) {
			count += dp[n][i];
		}

		System.out.println(count % MOD);
	}
}

문제

접근 방식

문제 자체는 14501번 퇴사 문제와 똑같지만 입력의 양이 최대 150만 개이기 때문에

이전에 풀었던 방식처럼 O(n^2)의 시간 복잡도로 풀면 시간 초과가 발생한다.

DP 테이블을 좀 더 효율적으로 채워 넣어야 시간 제한을 맞출 수 있으니

문제를 좀 더 자세하게 분석해보겠다.

우선 i번째 날에 t일의 시간이 소요되는 상담을 진행했다면

i + 1일에 p만큼의 돈을 지급받는다.

즉, i일 이전에 받은 돈들은 모두 정해진 기한 내에 완료하여 받을 수 있는 돈이고

i일에 받을 수 있는 가장 큰돈은 i일 이전의 값들 중 가장 큰 값이다.

n
10

t p
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

위와 같은 테스트 케이스가 주어졌을 때

1 ~ 5일까지의 상담들은 모두 6일에 완료되어 돈을 받을 수 있고

그중 가장 큰 값인 50원이 6일에 받을 수 있는 가장 큰 경우다.

다음으로 6일에 진행한 상담비는 하루 뒤인 7일에 받을 수 있고

7일에는 이전까지의 받은 돈 중 가장 큰 값인 50원에

당일 받을 10원을 더한 60원을 받을 수 있다.

7일에 진행한 상담비는 2일 뒤인 9일에 받을 수 있고

마찬가지로 현재까지 받은 돈 중 가장 큰 60원에

당일 받을 20원을 더한 80원을 받을 수 있다.

8일에 진행한 상담비는 3일 뒤인 퇴사날에 받을 수 있고

8일 이전의 가장 큰 값인 60원에 30원을 더한 90원을 받을 수 있다.

즉, 매 상담마다 두 가지를 계산해 주면 되는데

현재를 기준으로 가장 큰돈을 받을 수 있는 경우인 dp [i]와

현재 + 소요일에 받게 될 돈인 dp [i+t]를 구해주면 된다.

dp[i]는 현재 날짜와 이전 날짜 중에서 가장 큰 값을 골라주면 되니

dp[i] = max(dp[i], dp[i-1])

dp [i+t]는 현재 날짜에 받을 수 있는 가장 큰 돈 + 상담 완료 시 받을 돈 중에서

가장 큰 값을 골라줘야 하니

dp[i+t] = max(dp[i+t], dp[i] + p)

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());

		int[] dp = new int[n + 51];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());

			int time = Integer.parseInt(st.nextToken());
			int price = Integer.parseInt(st.nextToken());

			dp[i] = Math.max(dp[i], dp[i - 1]);
			dp[i + time] = Math.max(dp[i + time], dp[i] + price);
		}

		System.out.println(Math.max(dp[n], dp[n + 1]));
	}
}

문제

접근 방식

문제에 나와 있는 예시를 살펴보면

4일의 경우에는 1일과 3일 중 하나를 선택할 수 있고

둘 중 더 큰 값을 선택하는 것이 효율적이니

더 큰 값을 골라주면 된다. (예시에서 두 날의 값은 같아서 뭘 고르든 상관은 없다.)

즉, 현재 날을 기준으로 이전에 상담이 끝나는 요일들 중

가장 비용이 큰 값을 선택해주면 된다.

DP 테이블은 아래와 같이 정의했다.

dp[i] = i번째 날에 받을 수 있는 누적 금액

dp[i] = 1 ~ i-1까지의 날짜 중 i일 이전에 끝나고 가장 비용이 큰 값

위의 과정을 코드로 작성하면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());

		int[] times = new int[n + 1];
		int[] prices = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());

			times[i] = Integer.parseInt(st.nextToken());
			prices[i] = Integer.parseInt(st.nextToken());
		}

		int[] d = new int[n + 1];
		int result = 0;

		for (int i = 1; i <= n; i++) {
			if (i + times[i] - 1 > n) continue;

			int max = prices[i];

			for (int j = 1; j < i; j++) {
				if (j + times[j] - 1 < i) max = Math.max(prices[i] + d[j], max);
			}

			d[i] = max;
			result = Math.max(max, result);
		}

		System.out.println(result);
	}
}

문제

접근 방식

각 변의 길이가 1인 정삼각형으로 시작해 n번째 정삼각형의 한 변의 길이를 구해야 한다.

삼각형을 위와 같이 나선 모양으로 회전하면서 추가할 때

위와 같이 한 변의 길이가 이전 변의 길이보다 커질 때 새로운 삼각형을 추가해주고

이 때 새로운 정삼각형의 새로운 한 변의 길이는 dp[i] = dp[i - 1] + dp[i - 5]라는 것을 알 수 있다.

dp[i-5]를 계산하기 위해 dp 테이블의 dp[1] ~ dp[5]까지를

각각 순서대로 1, 1, 1, 2, 2로 초기화 해준 후에

dp[6] ~ dp[n]까지 구한 공식대로 계산해주면 된다.

계산하다 보면 인트형의 범위를 벗어나니 long 타입으로 저장해줘야 한다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		long[] dp = new long[101];

		dp[1] = 1;
		dp[2] = 1;
		dp[3] = 1;
		dp[4] = 2;
		dp[5] = 2;


		for (int i = 6; i <= 100; i++) {
			dp[i] = dp[i - 1] + dp[i - 5];
		}

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());

			sb.append(dp[n]).append("\n");
		}

		System.out.println(sb);
	}
}

문제

접근 방식

수열 {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이 주어졌을 때 1, 100, 2, 60, 50 처럼

들쑥날쑥한 부분 수열이 아닌 1, 2, 50, 60 처럼 증가하는 부분 수열 중에서

합이 가장 큰 부분 수열을 구해야 하는 문제다.

우선 간단하게 생각해보면 이전 수보다 큰 값이 나올 때까지 모두 합해주면

특정 수로 끝나는 부분 수열의 합을 구할 수는 있다.

1로 끝나는 부분 수열은 {1} = 1

1 > 100 > 2 (이전 수인 100보다 작음)
== 100으로 끝나는 부분 수열은 {1, 100} = 101

2 > 50 > 60 > 3 (이전 수인 60보다 작음)
== 60으로 끝나는 부분 수열은 {2, 50, 60} = 112

위와 같이 특정 수로 끝나는 부분 수열의 값을 알 수 있지만

문제에서 요구하는 부분 수열과는 조금 다르다.

문제에서는 {1, 2, 50, 60} = 113 처럼 연속된 부분 수열이 아니라도

값이 증가하기만 한다면 부분 수열로 만들 수 있기 때문에

{1, 2, 50, 60} 과 같은 수열을 만들기 위해서는

{1}과 {2, 50, 60}을 합치면 된다는 것을 알 수 있다.

즉, 60으로 끝나는 부분 수열의 합은

60보다 작은 부분 수열의 합들을 더한 값이 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int[] arr = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int max = arr[0];
		int[] dp = new int[n];
		dp[0] = arr[0];

		for (int i = 1; i < n; i++) {
			dp[i] = arr[i];
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					dp[i] = Math.max(dp[j] + arr[i], dp[i]);
				}
			}

			max = Math.max(max, dp[i]);
		}

		System.out.println(max);
	}
}

문제

접근 방식

어떻게 풀어야할지 모르겠어서 일단 각 자리수별로 만들 수 있는

경우들을 직접 나열해보고서 규칙을 찾아보았다.

1 

10

100
101

1000
1001
1010

10000
10001
10010
10100
10101

100000
100001
100010
100100
100101
101000
101001
101010

1000000
1000001
1000010
1000100
1000101
1001000
1001001
1001010
1010000
1010001
1010010
1010100
1010101

각 자리수별로 경우의 수를 세어보면 1, 1, 2, 3, 5, 8, 13, ...

이런식으로 증가하는 것을 알 수 있는데 어디서 많이 본거 같다면

생각하는 그 피보나치 수열이 맞다.

1과 2의 경우만 초기값을 1로 지정하고

3자리부터 dp[i - 1] + dp[i - 2]를 계산해주면서

테이블을 채워주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		long[] dp = new long[91];

		dp[1] = 1;
		dp[2] = 1;

		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i - 2] + dp[i - 1];
		}

		System.out.println(dp[n]);
	}
}

문제

접근 방식

기존 1로 만들기 문제에 1이 되는 순서까지 출력하는게 추가된 문제기에

기존 DP 테이블 외에도 순서를 기록할 배열을 더 만들어서 기록해주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int[] dp = new int[n + 1];
		int[] history = new int[n + 1];

		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + 1;
			history[i] = i - 1;

			if (i % 2 == 0 && dp[i] > dp[i/2] + 1) {
				dp[i] = dp[i/2] + 1;
				history[i] = i/2;
			}

			if (i % 3 == 0 && dp[i] > dp[i/3] + 1) {
				dp[i] = dp[i/3] + 1;
				history[i] = i/3;
			}
		}

		StringBuilder sb = new StringBuilder();

		sb.append(dp[n]).append("\n");

		int num = n;

		while (true) {
			sb.append(num).append(" ");
			if (num == 1) break;
			num = history[num];
		}

		System.out.println(sb);
	}
}

문제

접근 방식

Prefix Sum 알고리즘을 사용해 풀 수 있는 문제로

i ~ j까지의 구간합은 (i 까지의 합) - (j-1까지의 합)이라는 공식을 이용해

DP 테이블에는 i까지의 합들을 저장하고 위의 공식대로 계산해주면 된다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] dp = new int[n + 1];

		st = new StringTokenizer(br.readLine());
		dp[1] = Integer.parseInt(st.nextToken());

		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + Integer.parseInt(st.nextToken());
		}

		StringBuilder sb = new StringBuilder();

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());

			sb.append(dp[j] - dp[i - 1]).append("\n");
		}

		System.out.println(sb);
	}
}