📙[Algo] 24.03.07 ~ 24.03.08 알고리즘

알고리즘 문제) BOJ 15486. 퇴사 2

• 링크 : https://www.acmicpc.net/problem/5052

문제 요약

• 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거리

• 링크 : https://www.acmicpc.net/problem/1149

문제 요약

• N개의 집에 빨강(R), 파랑(B), 초록(G)을 칠하려고 하며, 집마다 각각의 색을 칠할 때 드는 비용이 존재한다.
• 단, 서로 인접한 집끼리 같은 색이 되지 않도록 해야 한다.
• 이때 비용의 최솟값 구하는 문제.

시간 제한

• 0.5초

입력

• 집의 수 N
  • 2≤N≤1000
• N개의 줄에 각 집을 R,G,B로 칠할 때 드는 비용이 주어짐
  • 비용은 1000이하의 자연수

출력

• 모든 집을 하는 비용의 최솟값

접근법

1. 완전탐색으로 접근하기
   • 각 집에서 특정 색을 선택했을 때의 모든 경우를 살펴본다.
   • 그러나 인접한 색은 다르다는 조건을 체크할 것
2. 백트랙킹으로 접근 한다면
   • 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이므로 백트랙킹으로 풀면 시간초과가 뜬다…
3. 최적화하기
   • DP로 풀 것
     • 최소비용을 반환하는 함수를 만들어야 한다.
       현재 집에서 선택할 수 있는 색깔 중 최소 비용을 반환할 수 있도록 만든다.
     • 메모이제이션을 추가해서 중복 계산 방지
       dp[cur][prevColor]에 값 저장

코드

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. 평범한 배낭

• 링크 : https://www.acmicpc.net/problem/12865

문제 요약

• N개의 물건이 존재하고, 각 물건은 무게 W, 가치 V를 갖고 있다.
• 최대 K만큼의 무게를 들 수 있을 때, 나올 수 있는 가치의 최댓값을 구하는 문제.

시간 제한

• 2초

입력

• 물품의 수 N, 버틸 수 있는 무게 K
  • 1≤N≤100
  • 1≤K≤10만
• N개의 줄에 각 물건의 무게 W, 물건의 가치 V가 주어짐
  • 1≤W≤10만
  • 0≤V≤1000

출력

• 배낭에 넣을 수 있는 물건들의 가치의 최댓값?

접근법

1. 완전탐색으로 생각하기
   • 물건을 선택하고, 안 하고 모든 경우를 살펴보면서 무게를 넘지 않는 경우에 한해서 가치의 최댓값 구하기
2. 백트랙킹으로 생각하기
   • recur(cur, weight, price)
     • 선택해면 weight와 price를 늘리고 넘겨준다
   • 가지치기 : weight가 초과하는 순간 return
3. 함수로 만들기
   • 현재 배낭을 선택했을 때, 안 했을 때 가치 합의 최댓값 출력
4. 메모이제이션

코드

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. 공룡게임

• 링크 : https://www.acmicpc.net/problem/20544

문제 요약

• 맵에는 N개의 지점이 있고, 각 지점은 높이가 1또는 2인 장애물이 존재한다
• 시작 지점은 1이고, 공룡이 앞으로 갈수록 지점을 나타내는 수가 증가한다.
• 공룡은 (1) 최대 2개의 인접한 장애물을 뛰어넘을 수 있으며(3개 이상 X), 두 장애물의 높이의 합이 4 이상이면 뛰어넘을 수 없다. (2) 시작 지점은 장애물이 없다. (3) 높이 2인 장애물은 무조건 하나 이상 존재해야 한다. N이 주어졌을 때 가능한 맵의 종류를 구하는 문제.

시간 제한

• 2초

입력

• 맵의 길이 N
  • 1≤N≤1000

출력

• 나올 수 있는 맵의 가짓수
  • 1000000007로 나눈 나머지로 출력

접근법

1. 완전탐색으로 생각하기
   • N지점에 장애물을 설치하거나 하지 않은 모든 경우를 살펴보면 가능한 경우만 카운트 한다.
2. 백트랙킹
   • recur(cur, nearCnt, nearTwoCnt, two)
     • nearCnt : 인접한 장애물 개수
     • nearTwoCnt : 인접한 높이 2짜리 장애물 개수
     • two : 장애물 2짜리 설치 여부
     • ⇒ 연속 3개 X (즉, nearCnt > 2이면 안 됨)
       ⇒ 인접한 장애물 높이 4이상 X(즉, nearTwoCnt ≥ 2이면 안 됨)
       ⇒ 높이 2짜리는 무조건 설치할 것(즉, two가 false면 안 됨)
       ⇒ 위 3가지로 가지치기
3. 함수로 만들기
   • 가능한 경우 return 1을 하고, 그 return 값들을 누적해서 합한다.
4. 메모이제이션

코드

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. 출근 경로

• 링크 : https://www.acmicpc.net/problem/5569

문제 요약

• 남북 방향 도로가 W, 동서 방향으로 도로가 h개
• 남북 방향으로 도로 번호가 1,2, …, w
• 동서 방향으로 도로 번호가 1,2, …., h
• 교차로 : (i,j)
• 시작 위치 : (1,1)
• 회사 위치 : (w,h)
• 회사에 가기 위해 동쪽→, 북쪽↑ 으로만 이동 가능
• 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다
• 회사에 출근할 수 있는 경로의 수는 몇 가지

시간 제한

• 1초

입력

• w와 h가 주어진다
  • 2 ≤ w, h ≤ 100

출력

• 상근이가 출근할 수 있는 경로의 개수를 100000로 나눈 나머지를 출력

접근법

1. 백트랙킹으로 생각하기
   • 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(가지치기)
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;
    }
}

코드

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();
    }
}