알고리즘 스터디 13주차
1. 파스칼 삼각형
문제
- 파스칼 삼각형이 주어지고, 어떤 지점(R, C)을 꼭짓점으로 하는 한 변이 W인 정삼각형의 내부에 있는 수들의 합을 구하라는 문제
풀이
- R + W이 최대 30밖에 되지 않는다. 따라서 이차원 배열을 하나 만들고 파스칼 값들을 구한 뒤, (R, C)부터 내려가면서 값들의 합을 구하면 된다.
소스
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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 R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
int[][] tri = new int[31][31];
tri[1][1] = 1;
for (int i = 2; i <= 30; i++) {
tri[i][1] = tri[i][i] = 1;
for (int j = 2; j < i; j++) {
tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
}
}
int answer = 0;
for (int j = R, i = 1; j < R + W; j++, i++) {
for (int k = C; k <= C + i - 1; k++) {
answer += tri[j][k];
}
}
System.out.println(answer);
}
}2. 선물 전달
문제
- 사람들은 각자 하나의 선물을 가지고 있고, 자신을 제외하고 다른 사람한테 선물을 주려고 한다. 모든 사람들은 하나의 선물을 받아야할 때, 선물을 나누는 경우의 수를 구하는 문제
풀이
- 먼저 N - 1명까지 선물을 나누는 경우의 수가 있다고 가정하자. 그러면 1명이 추가가 되었을 경우를 생각해보면 된다.
- N번째랑 (1 ~ N - 1)번째가 서로 나누어줄 경우
- N번째가 (1 ~ N - 1)번째에게 선물을 줄 경우(서로 X)
- 위 2가지 경우를 생각해보면 서로 나누어줄 경우는 N - 2명을 나누는 경우와 동일하고, N번째가 1번째에게 선물을 줬다고 가정하면 결국 N - 1번째가 선물을 나누어주는 경우와 동일하다. (기존에 1번으로 줄 얘를 N번으로 바꾸면 되므로)
소스
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.function.BiPredicate;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Main {
final static BufferedReader BUFFER_READER = new BufferedReader(new InputStreamReader(System.in));
final static long MOD = 1000000000L;
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(BUFFER_READER.readLine());
long[] dp = new long[1000001];
dp[1] = 0;
dp[2] = 1;
for(int i = 3; i <= N; i++) {
dp[i] = ((long)(i - 1) * ((dp[i - 1] + dp[i - 2]) % MOD)) % MOD;
}
System.out.println(dp[N]);
}
}3. 괄호
문제
- 길이가 N인 올바른 괄호열의 개수를 구하는 문제
풀이
- DP를 생각해볼 수 있다.
- DP[i][j] = 길이가 i일 경우, 열린 괄호의 개수가 j일 때 올바른 괄호열의 개수
- 그러면 결국 DP[N][0]이 정답이 될 수 있다. (j는 음수가 되면 올바른 괄호열이 될 수 없으므로)
소스
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
final static long MOD = 1000000007L;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
long[][] d = new long[5001][5001];
d[1][1] = 1;
for (int i = 1; i < 5000; i++) {
for (int j = 0; j <= 5000; j++) {
if (d[i][j] == 0) {
continue;
}
if (j - 1 >= 0) {
d[i + 1][j - 1] += d[i][j];
d[i + 1][j - 1] %= MOD;
}
if (j + 1 <= 5000) {
d[i + 1][j + 1] += d[i][j];
d[i + 1][j + 1] %= MOD;
}
}
}
while (T > 0) {
int n = Integer.parseInt(br.readLine());
if (n % 2 == 1) {
System.out.println(0);
} else {
System.out.println(d[n][0]);
}
T -= 1;
}
}
}
Wow