Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 8b92f9a

Browse files
authored
Merge pull request #355 from GreatAlgorithm-Study/dahye
[27주차] 고다혜
2 parents 6a59651 + 535815a commit 8b92f9a

File tree

5 files changed

+471
-0
lines changed

5 files changed

+471
-0
lines changed

‎BOJ/1000-5000번/DH_1644.java

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
import java.io.*;
2+
3+
/*
4+
* 소수의 연속합
5+
*/
6+
7+
public class DH_1644 {
8+
public static void main(String[] args) throws Exception {
9+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
10+
11+
int N = Integer.parseInt(br.readLine());
12+
13+
// N까지 숫자 중에서 어떤 것이 소수인지 알아내기
14+
boolean[] isNotPrime = getNotPrime(N);
15+
16+
System.out.println(getCount(isNotPrime, N));
17+
}
18+
19+
// 투포인터를 통해 소수의 연속합을 구했을 때, n이 되는 개수 구하기
20+
static int getCount(boolean[] isNotPrime, int n) {
21+
int count = 0;
22+
23+
int s = 2, e = 2, sum = 2;
24+
25+
while(s <= e && e < isNotPrime.length) {
26+
// e 옮기기
27+
if(sum < n) {
28+
29+
while(e < isNotPrime.length) {
30+
31+
e += 1;
32+
33+
if(isNotPrime.length == e) break;
34+
35+
if(!isNotPrime[e]) {
36+
sum += e;
37+
break;
38+
}
39+
}
40+
}
41+
42+
// sum >= n → s 옮기기
43+
else {
44+
if(sum == n) count += 1;
45+
46+
sum -= s;
47+
48+
while(s < e) {
49+
s += 1;
50+
51+
if(!isNotPrime[s]) {
52+
break;
53+
}
54+
}
55+
}
56+
}
57+
58+
return count;
59+
}
60+
61+
// 에라토스테네스 체로 n까지 숫자 중에서 소수 걸러내기
62+
static boolean[] getNotPrime(int n) {
63+
boolean[] isNotPrime = new boolean[n + 1];
64+
65+
isNotPrime[0] = true;
66+
isNotPrime[1] = true;
67+
68+
for(int i = 2; i <= Math.sqrt(isNotPrime.length); i++) {
69+
if(isNotPrime[i]) continue;
70+
71+
for(int j = i * i; j < isNotPrime.length; j += i) {
72+
isNotPrime[j] = true;
73+
}
74+
}
75+
76+
return isNotPrime;
77+
}
78+
}

‎BOJ/10001-15000번/DH_14852.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
import java.io.*;
2+
3+
/*
4+
* 타일 채우기 3
5+
*/
6+
7+
public class DH_14852 {
8+
static final int MOD = 1_000_000_007;
9+
10+
public static void main(String[] args) throws Exception {
11+
12+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
13+
int N = Integer.parseInt(br.readLine());
14+
15+
long[] dp = new long[Math.max(4, N + 1)];
16+
17+
dp[1] = 2;
18+
dp[2] = 7;
19+
20+
long sum = 2; // 기본으로 더해지는거
21+
22+
for(int i = 3; i < dp.length; i++) {
23+
// sum 에는 dp[i - 3] * 2 + dp[i - 4] * 2 + dp[i - 5] * 2 ...가 저장되어 있음
24+
dp[i] = (dp[i - 1] * 2 + dp[i - 2] * 3 + sum) % MOD;
25+
sum += dp[i - 2] * 2;
26+
}
27+
28+
System.out.println(dp[N] % MOD);
29+
}
30+
}

‎BOJ/15001-20000번/DH_18513.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import java.io.*;
2+
import java.util.*;
3+
4+
/*
5+
* 샘터
6+
* 주의점
7+
* 1. 샘터의 위치는 -100_000_000 ~ 100_000_000이지만, 집의 위치는 이걸 벗어날 수 있음
8+
* 2. 불행도를 계산할 때, 불행도의 범위 long으로 설정하기
9+
* - 1 + 2 + ... + 500,000 = 125,000,250,000
10+
*/
11+
12+
public class DH_18513 {
13+
14+
static final int INF = 100_200_000;
15+
16+
public static void main(String[] args) throws Exception {
17+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
18+
StringTokenizer st = new StringTokenizer(br.readLine());
19+
20+
int N = Integer.parseInt(st.nextToken()); // 샘터의 개수
21+
int K = Integer.parseInt(st.nextToken()); // 집의 개수
22+
23+
boolean[] v = new boolean[2 * INF + 1]; // -INF ~ INF
24+
Queue<int[]> q = new ArrayDeque<int[]>();
25+
26+
st = new StringTokenizer(br.readLine()); // 샘터에 대한 정보
27+
for(int i = 0; i < N; i++) {
28+
int current = Integer.parseInt(st.nextToken());
29+
q.add(new int[] {current, 0});
30+
v[current + INF] = true;
31+
}
32+
33+
int cnt = 0;
34+
int badCnt = 0;
35+
36+
L: while(!q.isEmpty()) {
37+
int[] current = q.poll();
38+
39+
// 좌, 우 확인하기
40+
for(int d = -1; d < 2; d += 2) {
41+
int next = current[0] + d;
42+
43+
if(next < -INF || next > INF || v[next + INF]) continue;
44+
cnt += 1;
45+
badCnt += current[1] + 1;
46+
47+
if(cnt ==K) break L;
48+
49+
q.add(new int[] {next, current[1] + 1});
50+
v[next + INF] = true;
51+
}
52+
}
53+
54+
System.out.println(badCnt);
55+
}
56+
}
Lines changed: 215 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,215 @@
1+
import java.io.*;
2+
import java.util.*;
3+
4+
/*
5+
* 조심해야 됐던 부분
6+
* - 나무가 성장하고 번식할 때, 벽의 정보가 없어지면 안됐음!
7+
*/
8+
9+
public class DH_나무박멸 {
10+
11+
static int N, M, K, C;
12+
static int totalRemoveTreeCnt, tmpRemoveTreeCnt;
13+
static int[][] map, remove; // map: 나무, remove: 제초제 지속 시간
14+
static int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0}, dc = {-1, 0, 1, 1, 1, 0, -1, -1}; // 8방 배열
15+
16+
public static void main(String[] args) throws Exception {
17+
initInput();
18+
solution();
19+
System.out.println(totalRemoveTreeCnt);
20+
}
21+
22+
static void solution() {
23+
24+
while(M-- > 0) {
25+
grow(); // 성장
26+
spread(); // 번식
27+
remove(); // 제초제 뿌리기
28+
decreaseRemove(); // 제초제 감소
29+
}
30+
}
31+
32+
// 제초제 지속 시간 1씩 줄이기
33+
static void decreaseRemove() {
34+
for(int r = 0; r < remove.length; r++) {
35+
for(int c = 0; c < remove[0].length; c++) {
36+
if(remove[r][c] == 0) continue;
37+
remove[r][c] -= 1;
38+
}
39+
}
40+
}
41+
42+
static void remove() {
43+
// 제초제가 뿌려진 칸에는 C년 만큼 제초제가 남아있다가 C + 1년째가 될 때 사라짐
44+
int removeTreeCnt = -1;
45+
46+
Queue<Integer> spreadPos = new ArrayDeque<Integer>(); // 제초제가 퍼져 나갈 위치
47+
48+
for(int r = 0; r < map.length; r++) {
49+
for(int c = 0; c < map[0].length; c++) {
50+
if(map[r][c] == -1) continue; // 벽이면 continue
51+
52+
tmpRemoveTreeCnt = 0; // (r, c)에서 제거할 수 있는 나무 수
53+
54+
Queue<Integer> tmp = getRemoveCnt(r, c);
55+
56+
if(tmpRemoveTreeCnt <= removeTreeCnt) continue;
57+
removeTreeCnt = tmpRemoveTreeCnt;
58+
59+
spreadPos = tmp;
60+
}
61+
}
62+
63+
totalRemoveTreeCnt += removeTreeCnt;
64+
65+
// 제초제 뿌려주기
66+
while(!spreadPos.isEmpty()) {
67+
int pos = spreadPos.poll();
68+
69+
int r = pos / N, c = pos % N;
70+
if(map[r][c] == -1) continue; // 벽일 경우 넘어가야 됨!!✨
71+
72+
map[r][c] = 0;
73+
remove[r][c] = (C + 1); // 제초제 뿌리기
74+
}
75+
}
76+
77+
static Queue<Integer> getRemoveCnt(int r, int c) {
78+
Queue<Integer> spreadPos = new ArrayDeque<>();
79+
80+
// (r, c)에서 대각선 4방으로 K칸 만큼 가기
81+
Queue<int[]> q = new ArrayDeque<>();
82+
83+
int pos = r * N + c;
84+
85+
// (r, c) 지점에서는 대각선 4방으로 보내기
86+
for(int dir = 0; dir < 8; dir += 2) {
87+
q.add(new int[] {pos, 0, dir});
88+
}
89+
90+
spreadPos.add(pos); // 제초제가 퍼지는 위치
91+
tmpRemoveTreeCnt += map[r][c];
92+
93+
while(!q.isEmpty()) {
94+
95+
int[] current = q.poll();
96+
int cr = current[0] / N;
97+
int cc = current[0] % N;
98+
int dir = current[2];
99+
100+
if(map[cr][cc] == 0) continue; // 처음에 (r, c)가 빈 공간으로 주어졌을 수도 있기 때문에 이거 처리해줘야 됨
101+
102+
int nr = cr + dr[dir];
103+
int nc = cc + dc[dir];
104+
105+
// 범위를 벗어나거나, 나무가 아예 없는 칸이거나, 뻗어간 거리가 K가 되었다면 continue
106+
if(!check(nr, nc) || current[1] == K) continue;
107+
108+
int nPos = nr * N + nc;
109+
spreadPos.add(nPos);
110+
111+
// 벽이 있거나, 나무가 아예 없는 칸은 그 칸 까지만 제초제가 뿌려짐
112+
if(map[nr][nc] <= 0) continue;
113+
114+
q.add(new int[] {nPos, current[1] + 1, dir});
115+
tmpRemoveTreeCnt += map[nr][nc];
116+
}
117+
return spreadPos;
118+
}
119+
120+
// 번식 - 벽, 다른 나무, 제초제 모두 없는 칸에 번식 진행 (번식이 가능한 칸의 개수만큼 나누어진 그루 수 만큼 번식)
121+
static void spread() {
122+
int[][] tmp = new int[N][N];
123+
124+
for(int r = 0; r < map.length; r++) {
125+
for(int c = 0; c < map[0].length; c++) {
126+
if(map[r][c] <= 0) continue;
127+
128+
int cnt = 0; // 번식이 가능한 칸의 개수
129+
130+
for(int d = 1; d < 8; d+= 2) {
131+
int nr = r + dr[d];
132+
int nc = c + dc[d];
133+
134+
// 범위를 벗어나거나, 벽 & 다른 나무가 있거나, 제초제가 있다면 continue
135+
if(!check(nr, nc) || map[nr][nc] != 0 || remove[nr][nc] != 0) continue;
136+
cnt++;
137+
}
138+
139+
for(int d = 1; d < 8; d+= 2) {
140+
int nr = r + dr[d];
141+
int nc = c + dc[d];
142+
143+
// 범위를 벗어나거나, 벽 & 다른 나무가 있거나, 제초제가 있다면 continue
144+
if(!check(nr, nc) || map[nr][nc] != 0 || remove[nr][nc] != 0) continue;
145+
tmp[nr][nc] += map[r][c] / cnt;
146+
}
147+
148+
}
149+
}
150+
151+
for(int r = 0; r < map.length; r++) {
152+
for(int c = 0; c < map[0].length; c++) {
153+
map[r][c] += tmp[r][c];
154+
}
155+
}
156+
}
157+
158+
// 성장 - 인접한 네 칸의 칸 중 나무가 있는 수만큼 나무 성장
159+
static void grow() {
160+
161+
int[][] tmp = new int[N][N]; // 동시에 성장해야 되므로, tmp 배열에 증감에 대한 정보 저장
162+
163+
for(int r = 0; r < map.length; r++) {
164+
for(int c = 0; c < map[0].length; c++) {
165+
if(map[r][c] <= 0) continue; // 나무가 아니라면 continue
166+
167+
int tree = 0;
168+
169+
// 인접한 네 칸
170+
for(int d = 1; d < 8; d += 2) {
171+
172+
int nr = r + dr[d];
173+
int nc = c + dc[d];
174+
175+
// 범위를 벗어나거나, 나무가 아닐 때
176+
if(!check(nr, nc) || map[nr][nc] <= 0) continue;
177+
tree += 1;
178+
}
179+
180+
tmp[r][c] += tree;
181+
}
182+
}
183+
184+
for(int r = 0; r < map.length; r++) {
185+
for(int c = 0; c < map[0].length; c++) {
186+
map[r][c] += tmp[r][c];
187+
}
188+
}
189+
}
190+
191+
static boolean check(int r, int c) {
192+
return r >= 0 && r < map.length && c >= 0 && c < map[0].length;
193+
}
194+
195+
static void initInput() throws Exception {
196+
System.setIn(new FileInputStream("./input/나무박멸.txt"));
197+
198+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
199+
StringTokenizer st = new StringTokenizer(br.readLine());
200+
201+
N = Integer.parseInt(st.nextToken()); // 격자의 크기
202+
M = Integer.parseInt(st.nextToken()); // 박멸이 진행되는 년 수
203+
K = Integer.parseInt(st.nextToken()); // 제초제의 확산 범위
204+
C = Integer.parseInt(st.nextToken()); // 제초제가 남아있는 년수
205+
206+
map = new int[N][N]; // 나무
207+
remove = new int[N][N]; // 제초제
208+
209+
for(int r = 0; r < map.length; r++) {
210+
st = new StringTokenizer(br.readLine());
211+
212+
for(int c = 0; c < map[0].length; c++) map[r][c] = Integer.parseInt(st.nextToken());
213+
}
214+
}
215+
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /