[๋ฐฑ์ค] ๐ฅ 14719 ๋น๋ฌผ
๐ ๋์ด๋
๐ฅ Gold 5
๐ ๋ฌธ์
https://www.acmicpc.net/problem/14719
๐ ํ์ด
์โฆ. ์ง์ง ์ด๋ ค์ ๋ค.
์ฒ์์ผ๋ก ๋์ ํ๋ ๊ณจ๋ ๋ฌธ์ ์๋๋ฐ ๋ฌธ์ ๋ด์ฉ์ ๊ฝค ์ฌ๋ฏธ์์ด ๋ณด์๋ค.
์ฒ์์ผ๋ก ๋ ์ค๋ฅธ ๊ฒ์ 2์ฐจ์ ๋ฐฐ์ด์ ์ง์ ๋
์ ๊ทธ๋ฆฐ ํ ์ข์ฐ์ ๋
์ด ์์ผ๋ฉด ๊ทธ ์ฌ์ด ๋น๊ณต๊ฐ๋งํผ finalCount
๋ฅผ +1 ํด์ฃผ๋ ์์ผ๋ก ๊ตฌํํ๊ธฐ๋ก ํ์๋ค.
์ฒ์์๋ ๋ค์๊ณผ ๊ฐ์ด ๊ตณ์ด Show()
ํจ์๋ฅผ ํตํด ํ์ฌ ๋
๋ชจ์์ ๋ณด์ฌ์ฃผ๋ ํจ์๋ฅผ ๋ง๋ค๋ ค๋ค๊ฐ ์ค๊ฐ์ ๊ผฌ์ฌ์ 4x4 ๊ฐ์ ์ ์ฌ๊ฐํ ๋
์ ์ ์ธํ ๋ค๋ฅธ ๋
๋ค์ ๋ต์ด ์๋์๋ค.
์๋ฌด๋ฆฌ ์ฐพ์๋ ๋์ฒด ๋ฌด์จ ์ค๋ฅ์ธ์ง ๋ชจ๋ฅด๊ฒ ์ด์ ๋ค์ ๊ณ ๋ฏผ์ ํ์๋ค.
public static void MakeBlocks(int height, int weight) {
block = new boolean[height][weight];
for (int i = 0; i < block.length; i++) {
Arrays.fill(block[i], false);
}
}
public static void FillBlocks(int index, int height) {
for (int i = 0; i < height; i++) {
block[index][i] = true;
}
}
public static void Show() {
for (int i = block[0].length - 1; i > -1; i--) {
for (int j = 0; j < block.length; j++) {
System.out.print(block[j][i] + "\t");
}
System.out.println("");
}
}
public static int Flow(int index, int width) {
boolean isBlock = false;
int FinalCount = 0;
int Count = 0;
for (int i = 0; i < width; i++) {
if (block[i][index]) {
isBlock = true;
FinalCount += Count;
} else {
if (isBlock) {
Count += 1;
}
}
}
return FinalCount;
}
๊ทธ๋ฌ๋ค๊ฐ ์์์ ์๊ธฐ๋ 1์ฐจ์ ๋ฐฐ์ด์ ํตํด์ ํ์๋ค๊ณ ํ๊ธธ๋ ๊ฐ์๊ธฐ ๋ฒ๋ฉ์ด๋ ์์ด๋์ด๊ฐ ํ๋๊ฐ ์๊ฐ์ด ๋ฌ๋ค.
๊ตณ์ด ๋ชจ๋ ๋
์ ๋ง๋ค ํ์๊ฐ ์์ด w ๋งํผ์ 1์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ ํ 1์ธต๋ถํฐ ๋
์ ๋ฃ์ํ ์ข์ฐ ๋ฒฝ์ด ์์ผ๋ฉด ๊ทธ์ฌ์ด ๋น๊ณต๊ฐ ๋งํผ finalCount
๋ฅผ +1 ํด์ฃผ๋ฉด ์ด๋จ๊น? ํ๋ ์๊ฐ์ด์๋ค.
ํ์ง๋ง ๋ง์ ๊ตฌํ์ ํ๋ ค๊ณ ํ๋ ์คํ๋ ค ๋ณต์กํด์ง๊ณ , ์ด์ ์ ํ๋ 2์ฐจ์ ๋ฐฐ์ด์ ์ด์ฉํ๋ ๊ฒ์ด ํจ์ฌ ๊ฐ๋จํ ๊ฒ ๊ฐ์๋ค.
๊ทธ๋์ 1์ฐจ์ ๋ฐฐ์ด๋ก ์์ฑํ๋ ์ฝ๋๋ฅผ ๋ค์ ์ญ์ ํ๊ณ , ์๋ก ์ฝ๋๋ฅผ ์ง๊ธฐ ์์ํด์๋ค.
๊ธฐ๋ณธ์ ์ผ๋ก ๋ฐ์ h, w๋งํผ 2์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ค๊ณ , ๊ทธ ์์ false
๋ก ์ด๊ธฐํ ํด์ฃผ์๋ค.
์ดํ FillBlock()
๋ผ๋ ํจ์์์ ๋ฐ์ h๋งํผ ๋ฐ์์๋ถํฐ true
๋ก ๋ฐ๊ฟ์ฃผ์๋ค.
๊ฐ์ฅ ์ค์ํ ๋ฌผ์ด ์ผ๋งํผ ์ฑ์ ๋์ง ์ฒดํฌ๋ฅผ ํ๋ ํจ์์ธ IsFlow()
ํจ์์์ boolean
type์ isBlock
๋ณ์๋ฅผ ๋ง๋ค๊ณ , int
type ์ count
์ finalCount
๋ฅผ ๋ง๋ค์๋ค.
์ดํ 1์ธต๋ถํฐ ์ฐจ๋ก๋๋ก ์ข์ธก์์ ์ฐ์ธก์ผ๋ก ๋ฐ๋ณต๋ฌธ์ ๋๋ฆฌ๋ฉด์, ์ง์ ํ ์์น์ block
์ true
๊ฐ ์์ผ๋ฉด isblock
์ true
๋ก ๋ฐ๊พธ๊ณ , finalCount
์ count
๋ฅผ ๋ํ๊ณ count
๋ฅผ 0์ผ๋ก ๋ง๋ค์๋ค.
๊ทธ๋ฆฌ๊ณ ๋ง์ฝ ๊ทธ ์์น์ block
์ด ๋น์ด์์ผ๋ฉด์ isblock
์ด false
๋ผ๋ฉด count
์ +1์ ํด์ฃผ์๋ค.
๊ทธ๋ฆฌ๊ณ ํจ์๊ฐ ๋๋๋ฉด fianlCount
๋ฅผ returnํด์ฃผ์๋ค.
์ ๋ง ๋คํ์ค๋ฝ๊ฒ๋ ์ด ์ฝ๋๋ ์๋ฌด ๋ฌธ์ ์์ด ํ๋ฒ์ ์ ์๋ํ์๋ค.
์ฒ์์ผ๋ก ํผ ๊ณจ๋5์ง๋ฆฌ ๋ฌธ์ ์๋๋ฐ, ๋ง์น ์ด๋ ค์ด ํํธ์ ๊ฒ์์ ํด๋ฆฌ์ด ํ๊ฑฐ๋ง๋ฅ ์จ๋ชธ์ ์ ์จ์ด ๋์๋ค.
๋ค์์๋ FIFO๋ QUE, STACk๊ฐ์ ์ฌ๋ฌ๊ฐ์ง ์๊ณ ๋ฆฌ์ฆ์ ๋ํด์ ๊ณต๋ถํ ํ, ๊ทธ์ชฝ ์ฝ๋ฉ ๋ฌธ์ ๋ ํ์ด๋ณผ ์๊ฐ์ด๋ค.
์ฝ๋๋ฅผ ์ด์ฌํ ์ง๋ ์๋์ด ์๋์ ์ข์ ๊ฐ์ด ๋ค์์ง๋ง, ๊ฒฐ๊ตญ ์ฑ๊ณตํ๋๊น ํ๋ฐ์๊ตญ ์ฑ์ฅํ ๋๋์ด ๋ค์ด์ ์ข์๋ค.
๐ Code
package Implements;
import java.io.*;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.concurrent.Flow;
public class N14719 {
public static boolean[][] block;
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 = new StringTokenizer(br.readLine());
int height = Integer.parseInt(st.nextToken());
int width = Integer.parseInt(st.nextToken());
block = new boolean[height][width];
for (int i = 0; i < height; i++) {
Arrays.fill(block[i], false);
}
st = new StringTokenizer(br.readLine());
int result = 0;
FillBlock(height, width, st);
for (int i = 0; i < height; i++) {
result += IsFlow(i, width);
}
System.out.println(result);
}
public static void FillBlock(int height, int width, StringTokenizer st) {
int flag = 0;
for (int w = 0; w < width; w++) {
int num = Integer.parseInt(st.nextToken());
for (int h = height - 1; h > height - num - 1; h--) {
block[h][w] = true;
}
}
}
public static int IsFlow(int height, int width) {
boolean isblock = false;
int count = 0;
int finalCount=0;
for (int i = 0; i < width; i++) {
if (block[height][i]) {
isblock = true;
finalCount += count;
count = 0;
} else{
if (isblock) {
count += 1;
}
}
}
return finalCount;
}
}
package (์ด๋ฆ); ๋ฅผ ๋๊ณ , class ์ด๋ฆ์ Main
์ผ๋ก ๋ณ๊ฒฝํ๋ฉด ๋๋ค.
๊ฐ์ธ ๊ณต๋ถ ๊ธฐ๋ก์ฉ ๋ธ๋ก๊ทธ์
๋๋ค.
ํ๋ฆฌ๊ฑฐ๋ ์ค๋ฅ๊ฐ ์์ ๊ฒฝ์ฐ ์ ๋ณดํด์ฃผ์๋ฉด ๊ฐ์ฌํ๊ฒ ์ต๋๋ค.๐