📙[Algo] 24.03.25 알고리즘

알고리즘 문제) BOJ 2644. 촌수계산

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

문제 요약

• 두 사람의 촌수 계산하기

시간 제한

• 2초

입력

• 1,2,3,…n의 연속된 번호로 각각 표시 된다.
• 첫쨰 줄 : 전체 사람의 수 n
• 둘째 줄 : 천수를 게산해야하는 서로 다른 두 사람의 번호
• 셋째 줄 : 부모 자식들 간의 관계 개수 m
• 넷째줄 부터 부모 자식간의 관계를 나타내는 번호 x, y
  • x는 y의 부모 번호

출력

• 두 사람의 촌수 출력
  • 없다면 -1

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int targetA, targetB;
    static int M;
    static boolean[] visited;
    static int[][] arr;
    static int answer = -1;

    static void dfs(int node, int cnt) {

        if (node == targetB) {
            answer = cnt;
            return;
        }

        visited[node] = true;

        for (int i = 1; i <= N; i++) {
            if (!visited[i] && arr[node][i] == 1) {
                dfs(i, cnt + 1);
            }
        }
    }

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

        st = new StringTokenizer(br.readLine());
        targetA = Integer.parseInt(st.nextToken());
        targetB = Integer.parseInt(st.nextToken());

        M = Integer.parseInt(br.readLine());

        arr = new int[N + 1][N + 1];
        int from, to;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());

            arr[from][to] = 1;
            arr[to][from] = 1;
        }

        visited = new boolean[N + 1];
        dfs(targetA, 0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 3109. 빵집

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

문제 요약

• R*C격자의 지도가 주어짐
• 첫째 열은 근처 빵집의 가스관, 마지막 열은 원웅이의 빵집
• 가스관과 원웅이의 빵집을 연결하는 파이파를 설치하려고 함
• 이때 건물이 있는 경우에는 파이프를 놓을 수 없음
• 모든 파이프는 첫째열에서 시작
  • 오른쪽, 오른쪽위대각선, 오른쪽아래대각선 연결 가능
  • 이떄 경로는 겹치면 안 됨(각 칸을 지나는 파이프는 하나)
• 설치가능한 파이프라인의 최대 개수?

시간 제한

• 1초

입력

• R C
  • 1≤R≤1만
  • 5≤C≤500
• R개의 줄에 지도가 주어짐
  • . : 빈칸, x : 건물

출력

• 놓을 수 있는 파이프라인의 최대 개수를 출력

접근법

가장 위로가는 것을 우선으로 하면서 dfs

visited 처리 주의….

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int R, C;
    static char[][] map;
    // 우상 우 우하
    static int[] delR = {-1, 0, 1};
    static int[] delC = {1, 1, 1};
    static boolean[][] visited;
    static int cnt;

    static boolean check(int row, int col) {
        return 0 <= row && 0 <= col && row < R && col < C
                && !visited[row][col] && map[row][col] == '.';
    }
    static boolean dfs(int row, int col) {

        if (col == C - 1) return true;

        int mrow, mcol;
        boolean ret;
        for (int i = 0; i < 3; i++) {
            mrow = row + delR[i];
            mcol = col + delC[i];

            if (!check(mrow, mcol)) continue;

            visited[mrow][mcol] = true;
            ret = dfs(mrow, mcol);

            if (ret) return ret;

//            visited[mrow][mcol] = false;
        }

        return false;
    }

    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());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        String input;
        for (int i = 0; i < R; i++) {
            input = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            if (dfs(i, 0)) cnt++;
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 14247. 나무 자르기

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

문제 요약

• N개의 나무가 있고, 하루에 하나씩 N일 산에 오르면 나무를 자름
• 나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오

시간 제한

• 2초

입력

• 나무 개수 N
  • 1≤N≤10만
• 첫날 올라갔을 때 나무의 길이들이 N개 주어짐
  • 1≤Hi≤10만
• 그 다음 줄에는 나무들이 하루에 자라는 길이 N개가 주어짐
  • 1≤Ai≤1만

출력

• 나무를 잘라서 구할 수 있는 최대 양?

접근법

N이 10만 개이므로 for문은 1개만 사용 가능

1일차	2일차	3일차	4일차	5일차
1(2)	3	5	7	9
3(7)	10	17	24	31
2(3)	5	8	11	14
4(4)	8	12	16	4
6(1)	7	8	9	10

 

1일차	2일차	3일차	4일차	5일차
1(2)	3	5	7	9
3(7)	10	17	24	31
2(3)	5	8	11	14
4(4)	8	12	16	4
100(2)	102	104	106	108

결국 나무를 자를 때 매일 성장하는 속도가 얼마나 되는지가 중요 ⇒ 같은 나무를 여러번 잘라도 최종적으로 얻을 수 있는 개수는 일정

그렇기 떄문에 자라는 속도가 느린 순서대로 잘라간다. ⇒ 자라는 속도만큼 내가 추가적으로 얻을 수 있는 양이라고 생각!

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static class Tree **implements Comparable<Tree>** {
        int idx;
        int grow;

        public Tree(int idx, int grow) {
            this.idx = idx;
            this.grow = grow;
        }

        @Override
        **public int compareTo(Tree o)** {
            if(**this.grow == o.grow**) return this.idx - o.idx;
            else return **this.grow - o.grow**;
        }
    }

    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;

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

        int[] trees = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        Tree[] growUp = new Tree[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            growUp[i] = new Tree(i, Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(growUp);

        long sum = 0;
        for (int i = 0; i < N; i++) {
            sum += (trees[growUp[i].idx] + (long) i * growUp[i].grow);
        }

        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}