Merge pull request #355 from GreatAlgorithm-Study/dahye

KodaHye · web-flow · commit 8b92f9a1d847 · 2025-03-30T22:17:40.000+09:00
[27주차] 고다혜
diff --git a/BOJ/1000-5000번/DH_1644.java b/BOJ/1000-5000번/DH_1644.java
@@ -0,0 +1,78 @@
+import java.io.*;
+
+/*
+ * 소수의 연속합
+ */
+
+public class DH_1644 {
+	public static void main(String[] args) throws Exception {
+		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+		
+		int N = Integer.parseInt(br.readLine());
+
+		// N까지 숫자 중에서 어떤 것이 소수인지 알아내기
+		boolean[] isNotPrime = getNotPrime(N);
+		
+		System.out.println(getCount(isNotPrime, N));
+	}
+	
+	// 투포인터를 통해 소수의 연속합을 구했을 때, n이 되는 개수 구하기
+	static int getCount(boolean[] isNotPrime, int n) {
+		int count = 0;
+		
+		int s = 2, e = 2, sum = 2;
+		
+		while(s <= e && e < isNotPrime.length) {
+			// e 옮기기
+			if(sum < n) {
+				
+				while(e < isNotPrime.length) {
+					
+					e += 1;
+
+					if(isNotPrime.length == e) break;
+					
+					if(!isNotPrime[e]) {
+						sum += e;
+						break;
+					}
+				}
+			}
+			
+			// sum >= n → s 옮기기 
+			else {
+				if(sum == n) count += 1;
+				
+				sum -= s;
+				
+				while(s < e) {
+					s += 1;
+					
+					if(!isNotPrime[s]) {
+						break;
+					}
+				}
+			}
+		}
+		
+		return count;
+	}
+
+	// 에라토스테네스 체로 n까지 숫자 중에서 소수 걸러내기
+	static boolean[] getNotPrime(int n) {
+		boolean[] isNotPrime = new boolean[n + 1];
+		
+		isNotPrime[0] = true;
+		isNotPrime[1] = true;
+		
+		for(int i = 2; i <= Math.sqrt(isNotPrime.length); i++) {
+			if(isNotPrime[i]) continue;
+			
+			for(int j = i * i; j < isNotPrime.length; j += i) {
+				isNotPrime[j] = true;
+			}
+		}
+		
+		return isNotPrime;
+	}
+}
diff --git a/BOJ/10001-15000번/DH_14852.java b/BOJ/10001-15000번/DH_14852.java
@@ -0,0 +1,30 @@
+import java.io.*;
+
+/*
+ * 타일 채우기 3
+ */
+
+public class DH_14852 {
+	static final int MOD = 1_000_000_007;
+	
+	public static void main(String[] args) throws Exception {
+		
+		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+		int N = Integer.parseInt(br.readLine());
+		
+		long[] dp = new long[Math.max(4, N + 1)];
+		
+		dp[1] = 2;
+		dp[2] = 7;
+		
+		long sum = 2; // 기본으로 더해지는거
+		
+		for(int i = 3; i < dp.length; i++) {
+			// sum 에는 dp[i - 3] * 2 + dp[i - 4] * 2 + dp[i - 5] * 2 ...가 저장되어 있음
+			dp[i] = (dp[i - 1] * 2 + dp[i - 2] * 3 + sum) % MOD;
+			sum += dp[i - 2] * 2;
+		}
+
+		System.out.println(dp[N] % MOD);
+	}
+}
diff --git a/BOJ/15001-20000번/DH_18513.java b/BOJ/15001-20000번/DH_18513.java
@@ -0,0 +1,56 @@
+import java.io.*;
+import java.util.*;
+
+/*
+ * 샘터
+ * 주의점
+ * 1. 샘터의 위치는 -100_000_000 ~ 100_000_000이지만, 집의 위치는 이걸 벗어날 수 있음
+ * 2. 불행도를 계산할 때, 불행도의 범위 long으로 설정하기
+ * - 1 + 2 + ... + 500,000 = 125,000,250,000
+ */
+
+public class DH_18513 {
+	
+	static final int INF = 100_200_000;
+	
+	public static void main(String[] args) throws Exception {
+		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+		StringTokenizer st = new StringTokenizer(br.readLine());
+		
+		int N = Integer.parseInt(st.nextToken()); // 샘터의 개수
+		int K = Integer.parseInt(st.nextToken()); // 집의 개수
+		
+		boolean[] v = new boolean[2 * INF + 1]; // -INF ~ INF
+		Queue<int[]> q = new ArrayDeque<int[]>();
+		
+		st = new StringTokenizer(br.readLine()); // 샘터에 대한 정보
+		for(int i = 0; i < N; i++) {
+			int current = Integer.parseInt(st.nextToken());
+			q.add(new int[] {current, 0});
+			v[current + INF] = true;
+		}
+		
+		int cnt = 0;
+		int badCnt = 0;
+		
+		L: while(!q.isEmpty()) {
+			int[] current = q.poll();
+			
+			// 좌, 우 확인하기
+			for(int d = -1; d < 2; d += 2) {
+				int next = current[0] + d;
+				
+				if(next < -INF || next > INF || v[next + INF]) continue;
+				cnt += 1;
+				badCnt += current[1] + 1;
+				
+				if(cnt ==K) break L;
+
+				q.add(new int[] {next, current[1] + 1});
+				v[next + INF] = true;
+			}
+		}
+		
+		System.out.println(badCnt);
+	}
+}
diff --git a/CodeTree/2021-2022년/DH_나무박멸.java b/CodeTree/2021-2022년/DH_나무박멸.java
@@ -0,0 +1,215 @@
+import java.io.*;
+import java.util.*;
+
+/*
+ * 조심해야 됐던 부분
+ * - 나무가 성장하고 번식할 때, 벽의 정보가 없어지면 안됐음!
+ */
+
+public class DH_나무박멸 {
+	
+	static int N, M, K, C;
+	static int totalRemoveTreeCnt, tmpRemoveTreeCnt;
+	static int[][] map, remove; // map: 나무, remove: 제초제 지속 시간
+	static int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0}, dc = {-1, 0, 1, 1, 1, 0, -1, -1}; // 8방 배열
+	
+	public static void main(String[] args) throws Exception {
+		initInput();
+		solution();
+		System.out.println(totalRemoveTreeCnt);
+	}
+	
+	static void solution() {
+		
+		while(M-- > 0) {
+			grow(); // 성장
+			spread(); // 번식
+			remove(); // 제초제 뿌리기
+			decreaseRemove(); // 제초제 감소
+		}
+	}
+	
+	// 제초제 지속 시간 1씩 줄이기
+	static void decreaseRemove() {
+		for(int r = 0; r < remove.length; r++) {
+			for(int c = 0; c < remove[0].length; c++) {
+				if(remove[r][c] == 0) continue;
+				remove[r][c] -= 1;
+			}
+		}
+	}
+	
+	static void remove() {
+		// 제초제가 뿌려진 칸에는 C년 만큼 제초제가 남아있다가 C + 1년째가 될 때 사라짐
+		int removeTreeCnt = -1;
+		
+		Queue<Integer> spreadPos = new ArrayDeque<Integer>(); // 제초제가 퍼져 나갈 위치
+		
+		for(int r = 0; r < map.length; r++) {
+			for(int c = 0; c < map[0].length; c++) {
+				if(map[r][c] == -1) continue; // 벽이면 continue
+				
+				tmpRemoveTreeCnt = 0; // (r, c)에서 제거할 수 있는 나무 수
+				
+				Queue<Integer> tmp = getRemoveCnt(r, c);
+				
+				if(tmpRemoveTreeCnt <= removeTreeCnt) continue;
+				removeTreeCnt = tmpRemoveTreeCnt;
+
+				spreadPos = tmp;
+			}
+		}
+		
+		totalRemoveTreeCnt += removeTreeCnt;
+		
+		// 제초제 뿌려주기
+		while(!spreadPos.isEmpty()) {
+			int pos = spreadPos.poll();
+			
+			int r = pos / N, c = pos % N;
+			if(map[r][c] == -1) continue; // 벽일 경우 넘어가야 됨!!✨
+			
+			map[r][c] = 0;
+			remove[r][c] = (C + 1); // 제초제 뿌리기
+		}
+	}
+	
+	static Queue<Integer> getRemoveCnt(int r, int c) {
+		Queue<Integer> spreadPos = new ArrayDeque<>();
+
+		// (r, c)에서 대각선 4방으로 K칸 만큼 가기
+		Queue<int[]> q = new ArrayDeque<>();
+		
+		int pos = r * N + c;
+		
+		// (r, c) 지점에서는 대각선 4방으로 보내기
+		for(int dir = 0; dir < 8; dir += 2) {
+			q.add(new int[] {pos, 0, dir});
+		}
+		
+		spreadPos.add(pos); // 제초제가 퍼지는 위치
+		tmpRemoveTreeCnt += map[r][c];
+		
+		while(!q.isEmpty()) {
+			
+			int[] current = q.poll();
+			int cr = current[0] / N;
+			int cc = current[0] % N;
+			int dir = current[2];
+			
+			if(map[cr][cc] == 0) continue; // 처음에 (r, c)가 빈 공간으로 주어졌을 수도 있기 때문에 이거 처리해줘야 됨
+			
+			int nr = cr + dr[dir];
+			int nc = cc + dc[dir];
+			
+			// 범위를 벗어나거나, 나무가 아예 없는 칸이거나, 뻗어간 거리가 K가 되었다면 continue
+			if(!check(nr, nc) || current[1] == K) continue;
+			
+			int nPos = nr * N + nc;
+			spreadPos.add(nPos);
+
+			// 벽이 있거나, 나무가 아예 없는 칸은 그 칸 까지만 제초제가 뿌려짐
+			if(map[nr][nc] <= 0) continue;
+			
+			q.add(new int[] {nPos, current[1] + 1, dir});
+			tmpRemoveTreeCnt += map[nr][nc];
+		}
+		return spreadPos;
+	}
+	
+	// 번식 - 벽, 다른 나무, 제초제 모두 없는 칸에 번식 진행 (번식이 가능한 칸의 개수만큼 나누어진 그루 수 만큼 번식)
+	static void spread() {
+		int[][] tmp = new int[N][N];
+		
+		for(int r = 0; r < map.length; r++) {
+			for(int c = 0; c < map[0].length; c++) {
+				if(map[r][c] <= 0) continue;
+				
+				int cnt = 0; // 번식이 가능한 칸의 개수
+				
+				for(int d = 1; d < 8; d+= 2) {
+					int nr = r + dr[d];
+					int nc = c + dc[d];
+					
+					// 범위를 벗어나거나, 벽 & 다른 나무가 있거나, 제초제가 있다면 continue
+					if(!check(nr, nc) || map[nr][nc] != 0 || remove[nr][nc] != 0) continue;
+					cnt++;
+				}
+				
+				for(int d = 1; d < 8; d+= 2) {
+					int nr = r + dr[d];
+					int nc = c + dc[d];
+					
+					// 범위를 벗어나거나, 벽 & 다른 나무가 있거나, 제초제가 있다면 continue
+					if(!check(nr, nc) || map[nr][nc] != 0 || remove[nr][nc] != 0) continue;
+					tmp[nr][nc] += map[r][c] / cnt;
+				}
+				
+			}
+		}
+		
+		for(int r = 0; r < map.length; r++) {
+			for(int c = 0; c < map[0].length; c++) {
+				map[r][c] += tmp[r][c];
+			}
+		}
+	}
+	
+	// 성장 - 인접한 네 칸의 칸 중 나무가 있는 수만큼 나무 성장
+	static void grow() {
+		
+		int[][] tmp = new int[N][N]; // 동시에 성장해야 되므로, tmp 배열에 증감에 대한 정보 저장
+		
+		for(int r = 0; r < map.length; r++) {
+			for(int c = 0; c < map[0].length; c++) {
+				if(map[r][c] <= 0) continue; // 나무가 아니라면 continue
+				
+				int tree = 0;
+				
+				// 인접한 네 칸
+				for(int d = 1; d < 8; d += 2) {
+					
+					int nr = r + dr[d];
+					int nc = c + dc[d];
+					
+					// 범위를 벗어나거나, 나무가 아닐 때
+					if(!check(nr, nc) || map[nr][nc] <= 0) continue;
+					tree += 1;
+				}
+				
+				tmp[r][c] += tree;
+			}
+		}
+		
+		for(int r = 0; r < map.length; r++) {
+			for(int c = 0; c < map[0].length; c++) {
+				map[r][c] += tmp[r][c];
+			}
+		}
+	}
+	
+	static boolean check(int r, int c) {
+		return r >= 0 && r < map.length && c >= 0 && c < map[0].length;
+	}
+	
+	static void initInput() throws Exception {
+		System.setIn(new FileInputStream("./input/나무박멸.txt"));
+		
+		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
+		StringTokenizer st = new StringTokenizer(br.readLine());
+		
+		N = Integer.parseInt(st.nextToken()); // 격자의 크기
+		M = Integer.parseInt(st.nextToken()); // 박멸이 진행되는 년 수
+		K = Integer.parseInt(st.nextToken()); // 제초제의 확산 범위
+		C = Integer.parseInt(st.nextToken()); // 제초제가 남아있는 년수
+		
+		map = new int[N][N]; // 나무
+		remove = new int[N][N]; // 제초제
+		
+		for(int r = 0; r < map.length; r++) {
+			st = new StringTokenizer(br.readLine());
+			
+			for(int c = 0; c < map[0].length; c++) map[r][c] = Integer.parseInt(st.nextToken());
+		}
+	}
+}
diff --git a/Programmers/Level3/DH_72413.java b/Programmers/Level3/DH_72413.java
