📙 Algorithm Solving/Java
📙[Algo] 24.03.07 ~ 24.03.08 알고리즘
혜덕hyeduck
2024. 3. 9. 11:10
알고리즘 문제) BOJ 15486. 퇴사 2
문제 요약
- N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담
- 하루에 하나씩 서로 다른 사람의 상담
- 담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi
시간 제한
- 1초
입력
- N (1 ≤ N ≤ 1500000)
- N개의 줄에 Ti와 Pi
- 1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000
출력
- 백준이가 얻을 수 있는 최대 이익
코드
- 시간초과 뜬 코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][] arr;
static int[] dp;
static int recur(int cur) {
if (cur > N) return -1000000000;
if (cur == N) return 0;
if (dp[cur] != -1) return dp[cur];
int ret = Math.max(recur(cur + arr[cur][0]) + arr[cur][1], recur(cur + 1));
dp[cur] = ret;
return dp[cur];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
arr = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 2; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new int[N];
Arrays.fill(dp, -1);
bw.write(String.valueOf( recur(0)));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1149. RGB거리
문제 요약
- N개의 집에 빨강(R), 파랑(B), 초록(G)을 칠하려고 하며, 집마다 각각의 색을 칠할 때 드는 비용이 존재한다.
- 단, 서로 인접한 집끼리 같은 색이 되지 않도록 해야 한다.
- 이때 비용의 최솟값 구하는 문제.
시간 제한
- 0.5초
입력
- 집의 수 N
- 2≤N≤1000
- N개의 줄에 각 집을 R,G,B로 칠할 때 드는 비용이 주어짐
- 비용은 1000이하의 자연수
출력
- 모든 집을 하는 비용의 최솟값
접근법
- 완전탐색으로 접근하기
- 각 집에서 특정 색을 선택했을 때의 모든 경우를 살펴본다.
- 그러나 인접한 색은 다르다는 조건을 체크할 것
- 백트랙킹으로 접근 한다면
- recur(cur, prevColor, total)
- cur : 현재 집
prevColor : 이전에 칠한 색깔
total : 비용 - recur(cur+1, 0, total+arr[cur][0])
recur(cur+1, 1, total+arr[cur][1])
recur(cur+1, 2, total+arr[cur][2]) - 그러나 N의 범위가 1000이므로 백트랙킹으로 풀면 시간초과가 뜬다…
- 최적화하기
- DP로 풀 것
- 최소비용을 반환하는 함수를 만들어야 한다.
현재 집에서 선택할 수 있는 색깔 중 최소 비용을 반환할 수 있도록 만든다. - 메모이제이션을 추가해서 중복 계산 방지
dp[cur][prevColor]에 값 저장
- 최소비용을 반환하는 함수를 만들어야 한다.
- DP로 풀 것
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N; // 집의 수
static int[][] arr; // 집마다 RGB를 설치했을 때 드는 비용
static int[][] dp; // 최소 비용 메모이제이션
static int recur(int cur, int prevColor) {
int ret = 1 << 30;
if (cur == N) {
return 0;
}
if (dp[cur][prevColor] != -1) {
return dp[cur][prevColor];
}
for (int i = 1; i <= 3; i++) {
if (i == prevColor) continue;
ret = Math.min(ret, recur(cur + 1, i) + arr[cur][i]);
}
dp[cur][prevColor] = ret;
return ret;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
arr = new int[N][4];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
arr[i][3] = Integer.parseInt(st.nextToken());
}
dp = new int[N][4];
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1);
}
bw.write(String.valueOf(recur(0, 0)));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 12865. 평범한 배낭
문제 요약
- N개의 물건이 존재하고, 각 물건은 무게 W, 가치 V를 갖고 있다.
- 최대 K만큼의 무게를 들 수 있을 때, 나올 수 있는 가치의 최댓값을 구하는 문제.
시간 제한
- 2초
입력
- 물품의 수 N, 버틸 수 있는 무게 K
- 1≤N≤100
- 1≤K≤10만
- N개의 줄에 각 물건의 무게 W, 물건의 가치 V가 주어짐
- 1≤W≤10만
- 0≤V≤1000
출력
- 배낭에 넣을 수 있는 물건들의 가치의 최댓값?
접근법
- 완전탐색으로 생각하기
- 물건을 선택하고, 안 하고 모든 경우를 살펴보면서 무게를 넘지 않는 경우에 한해서 가치의 최댓값 구하기
- 백트랙킹으로 생각하기
- recur(cur, weight, price)
- 선택해면 weight와 price를 늘리고 넘겨준다
- 가지치기 : weight가 초과하는 순간 return
- recur(cur, weight, price)
- 함수로 만들기
- 현재 배낭을 선택했을 때, 안 했을 때 가치 합의 최댓값 출력
- 메모이제이션
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, K;
static int[][] arr;
static int[][] dp;
static int recur(int cur, int weight) {
if (weight > K) return -1000000000;
if (cur == N) return 0;
if (dp[cur][weight] != -1) return dp[cur][weight];
int ret = Math.max(recur(cur + 1, weight + arr[cur][0]) + arr[cur][1], recur(cur + 1, weight));
dp[cur][weight] = ret;
return dp[cur][weight];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
dp = new int[N][100010];
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1);
}
bw.write(String.valueOf(recur(0, 0)));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 20544. 공룡게임
문제 요약
- 맵에는 N개의 지점이 있고, 각 지점은 높이가 1또는 2인 장애물이 존재한다
- 시작 지점은 1이고, 공룡이 앞으로 갈수록 지점을 나타내는 수가 증가한다.
- 공룡은 (1) 최대 2개의 인접한 장애물을 뛰어넘을 수 있으며(3개 이상 X), 두 장애물의 높이의 합이 4 이상이면 뛰어넘을 수 없다. (2) 시작 지점은 장애물이 없다. (3) 높이 2인 장애물은 무조건 하나 이상 존재해야 한다. N이 주어졌을 때 가능한 맵의 종류를 구하는 문제.
시간 제한
- 2초
입력
- 맵의 길이 N
- 1≤N≤1000
출력
- 나올 수 있는 맵의 가짓수
- 1000000007로 나눈 나머지로 출력
접근법
- 완전탐색으로 생각하기
- N지점에 장애물을 설치하거나 하지 않은 모든 경우를 살펴보면 가능한 경우만 카운트 한다.
- 백트랙킹
- recur(cur, nearCnt, nearTwoCnt, two)
- nearCnt : 인접한 장애물 개수
- nearTwoCnt : 인접한 높이 2짜리 장애물 개수
- two : 장애물 2짜리 설치 여부
- ⇒ 연속 3개 X (즉, nearCnt > 2이면 안 됨)
⇒ 인접한 장애물 높이 4이상 X(즉, nearTwoCnt ≥ 2이면 안 됨)
⇒ 높이 2짜리는 무조건 설치할 것(즉, two가 false면 안 됨)
⇒ 위 3가지로 가지치기
- recur(cur, nearCnt, nearTwoCnt, two)
- 함수로 만들기
- 가능한 경우 return 1을 하고, 그 return 값들을 누적해서 합한다.
- 메모이제이션
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[][][][] dp;
static long recur(int cur, int nearCnt, int nearTwoCnt, int two) {
if (nearCnt > 2 || nearTwoCnt >= 2) return 0;
if (cur == N) {
if (two == 1) return 1;
else return 0;
}
if (dp[cur][nearCnt][nearTwoCnt][two] != -1) return dp[cur][nearCnt][nearTwoCnt][two];
dp[cur][nearCnt][nearTwoCnt][two] = (int)((recur(cur + 1, 0, 0, two)
+ recur(cur + 1, nearCnt + 1, 0, two)
+ recur(cur + 1, nearCnt + 1, nearTwoCnt + 1, 1)) % 1000000007);
return dp[cur][nearCnt][nearTwoCnt][two];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
dp = new int[N][3][2][2];
for (int[][][] el1 : dp) {
for (int[][] el2 : el1) {
for (int[] el3 : el2) {
Arrays.fill(el3, -1);
}
}
}
bw.write(String.valueOf(recur(1,0,0,0)));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 5569. 출근 경로
문제 요약
- 남북 방향 도로가 W, 동서 방향으로 도로가 h개
- 남북 방향으로 도로 번호가 1,2, …, w
- 동서 방향으로 도로 번호가 1,2, …., h
- 교차로 : (i,j)
- 시작 위치 : (1,1)
- 회사 위치 : (w,h)
- 회사에 가기 위해 동쪽→, 북쪽↑ 으로만 이동 가능
- 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다
- 회사에 출근할 수 있는 경로의 수는 몇 가지
시간 제한
- 1초
입력
- w와 h가 주어진다
- 2 ≤ w, h ≤ 100
출력
- 상근이가 출근할 수 있는 경로의 개수를 100000로 나눈 나머지를 출력
접근법
- 백트랙킹으로 생각하기
- recur(right, top, prvDir, change)
- right : 우측으로 이동한 횟수
- top : 위로 이동한 횟수
- prvDir : 이전 이동 방향(1 북, -1 동)
- change : 연속 회전 여부
- 가지치기
- if (right > (w-1) || top > (h-1) || change ≥ 2) return
- if (right == w && top == h)
- cnt++;
- 이전 방향이 동쪽인 경우
- 또 동쪽으로 이동하면 회전이 아니므로 change = 0
- 북쪽으로 이동하면 회전이므로 change+1
- 이전 방향이 북쪽인 경우
- 또 북쪽으로 이동하면 회전이 아니므로 change = 0
- 동쪽으로 이동하면 회전이므로 change+1
- change가 2보다 크거나 같으면 연속으로 회전한 것이므로 return(가지치기)
- recur(right, top, prvDir, change)
- 함수로 바꾸기
static int recur(int right, int top, int prvDir, int change) {
if (right > w - 1 || top > h - 1 || change >= 2) return 0;
if (right == w - 1 && top == h - 1) return 1;
if (prvDir == -1) {
return (recur(right + 1, top, -1, 0) + recur(right, top + 1, 1, change + 1)) % 100000;
} else if (prvDir == 1) {
return (recur(right + 1, top, -1, change + 1) + recur(right, top + 1, 1, 0)) % 100000;
} else {
return (recur(right + 1, top, -1, 0) + recur(right, top + 1, 1, 0)) % 100000;
}
}
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int w, h;
static int[][][][] dp;
// 1. 백트랙킹 코드
// static void recur(int right, int top, int prvDir, int change) {
// prvDir : 이전 방향 / change : 연속 회전 횟수
//
// if (right > w - 1 || top > h - 1 || change >= 2) return;
//
// if (right == w - 1 && top == h - 1) cnt++; cnt %= 100000;
//
// if (prvDir == -1) {
// recur(right + 1, top, -1, 0);
// recur(right, top + 1, 1, change + 1);
// } else if (prvDir == 1) {
// recur(right + 1, top, -1, change + 1);
// recur(right, top + 1, 1, 0);
// } else {
// recur(right + 1, top, -1, 0);
// recur(right, top + 1, 1, 0);
// }
//
// }
// 2. 함수로 바꾸기
// static int recur(int right, int top, int prvDir, int change) {
//
// if (right > w - 1 || top > h - 1 || change >= 2) return 0;
//
// if (right == w - 1 && top == h - 1) return 1;
//
// if (prvDir == -1) {
// return (recur(right + 1, top, -1, 0) + recur(right, top + 1, 1, change + 1)) % 100000;
// } else if (prvDir == 1) {
// return (recur(right + 1, top, -1, change + 1) + recur(right, top + 1, 1, 0)) % 100000;
// } else {
// return (recur(right + 1, top, -1, 0) + recur(right, top + 1, 1, 0)) % 100000;
// }
// }
// 3. 메모이제이션 추가
static long recur(int right, int top, int prvDir, int change) {
if (right > w - 1 || top > h - 1 || change >= 2) return 0;
if (right == w - 1 && top == h - 1) return 1;
if (dp[right][top][prvDir][change] != -1) return dp[right][top][prvDir][change];
long ret;
if (prvDir == 1) {
ret = (recur(right + 1, top, 1, 0) + recur(right, top + 1, 2, change + 1));
} else if (prvDir == 2) {
ret = (recur(right + 1, top, 1, change + 1) + recur(right, top + 1, 2, 0));
} else {
ret = (recur(right + 1, top, 1, 0) + recur(right, top + 1, 2, 0));
}
dp[right][top][prvDir][change] = (int)(ret % 100000);
return dp[right][top][prvDir][change];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
dp = new int[w][h][3][3];
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
for (int k = 0; k < 3; k++) {
Arrays.fill(dp[i][j][k], -1);
}
}
}
bw.write(String.valueOf(recur(0, 0, 0, 0)));
bw.flush();
bw.close();
br.close();
}
}