📙 Algorithm Solving/Java
📙[Algo] 24.03.25 알고리즘
혜덕hyeduck
2024. 3. 26. 12:29
알고리즘 문제) BOJ 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. 빵집
문제 요약
- 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. 나무 자르기
문제 요약
- 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();
}
}