๋ชฉ์ฐจ
https://www.acmicpc.net/problem/1074
๋ฌธ์ ํ์ด
์๊ฐ์ด๊ณผ
๋ณด๋๋ฅผ ๋ฐ๋ณต์ ์ผ๋ก 4๋ฑ๋ถํ์ฌ Z ๋ชจ์์ผ๋ก ์ฝ์ด์ผํ๋ค.
๋ถํ ์ ๋ณต์ ์๊ฐํด์ ํ์์ง๋ง.. ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค.
ํ์ ๋ฒ์ ์ขํ๊ธฐ
๋ฌธ์ ๋ฅผ ๋ค์ ์ดํด๋ณด์
61์ ์ฐพ์ผ๋ ค๋ฉด ๊ตณ์ด ๋ชจ๋ ๋ถ๋ถ์ ํ์ํด์ผํ ๊น?
์๋๋ค. 4๋ฑ๋ถํ ์ฐ์ธกํ๋จ์ผ๋ก ๋ฒ์๋ฅผ ์ขํ๊ณ
๋ค์ ์ฐ์ธกํ๋จ์ผ๋ก ๋ฒ์๋ฅผ ์ขํ์ Z ํ์ํ๋ฉด๋๋ค.
๊ทธ๋ผ 61(6, 7)์ด ์ฐ์ธกํ๋จ์ ์์นํ๋ ๊ฒ์ ์ด๋ป๊ฒ ์ฐพ์๋ด๋ฉด๋ ๊น?
N์ด 8์ผ๋
X | Y | ||
์ผ์ชฝ | 0~3 | ์ | 0~3 |
์ค๋ฅธ์ชฝ | 4~7 | ์๋ | 4~7 |
์ผ์ชฝ์ X๊ฐ 0~3๊น์ง, ์ค๋ฅธ์ชฝ์ X๊ฐ 4~7๊น์ง์ด๋ค.
์๋ Y๊ฐ 0~3๊น์ง, ์๋๋ Y๊ฐ 4~7๊น์ง์ด๋ค.
61์ X์ธ 6์ 4~7์ ํด๋นํ๋ ์ค๋ฅธ์ชฝ
61์ Y์ธ 7์ 4~7์ ํด๋นํ๋ ์๋์ ํด๋น๋๋ค.
=============================================================
N์ด 4์ผ๋
X | Y | ||
์ผ์ชฝ | 4~5 | ์ | 4~5 |
์ค๋ฅธ์ชฝ | 6~7 | ์๋ | 6~7 |
์ผ์ชฝ์ X๊ฐ 4~5๊น์ง, ์ค๋ฅธ์ชฝ์ X๊ฐ 6~7๊น์ง์ด๋ค.
์๋ Y๊ฐ 4~5๊น์ง, ์๋๋ Y๊ฐ 6~7๊น์ง์ด๋ค.
61์ X์ธ 6์ 6~7์ ํด๋นํ๋ ์ค๋ฅธ์ชฝ
61์ Y์ธ 7์ 6~7์ ํด๋นํ๋ ์๋์ ํด๋น๋๋ค.
=============================================================
N์ด 2์ผ๋๋ Z ํ์์ด ๊ฐ๋ฅํด์ง๋ค. Zํ์ ํ๋ฉด์๋ +1์ฉ ์ฆ๊ฐํ ๊ฒ์ด๊ณ ,
(6, 7)์ ํ์ํ ๋ count๊ฐ 61์ด ๋๋ ค๋ฉด
N์ด 2์ธ ํ์์ ์์ํ๊ธฐ ์ ์ count๊ฐ 60์ด ๋์ด์์ด์ผํ๋ค!!!!
4๊ฐํ์ ์ฒซ๋ฒ์งธ ๊ฐ ํ์ ํ๊ธฐ
count๋ฅผ ์์๋ด๋ ค๋ฉด ์ชผ๊ฐ์ง ๋ฒ์์ ์ฒซ๋ฒ์งธ ๊ฐ์ ํ์ ํ๋ฉด๋๋ค.
N์ด 8์ผ๋ 4๋ฑ๋ถํ๋ฉด Half๋ 4( 8/2 = 4 ), ๊ฐ ์ฒซ๋ฒ์งธ ์์๊ฐ์ [0, 16, 32, 48] ์ด๋ค.
0 = (4 * 4) * 0
16 = (4 * 4) * 1
32 = (4 * 4) * 2
48 = (4 * 4) * 3
....
N์ด 4์ผ๋ 4๋ฑ๋ถํ๋ฉด Half๋ 2( 4/2 = 2 ), ๊ฐ ์ฒซ๋ฒ์งธ ์์๊ฐ์ [0, 4, 8, 12, 16, 20, 24, 28....] ์ด๋ค.
0 = (2 * 2) * 0
4 = (2 * 2) * 1
8 = (2 * 2) * 2
12 = (2 * 2) * 3
....
๊ท์น๋ ์ฐพ์์ผ๋ ์ด์ ์ฝ๋๋ก ์์ฑํด๋ณด์
์ ์ถ์ฝ๋
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int count = 0;
static int findX;
static int findY;
static boolean find = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
findY = Integer.parseInt(st.nextToken()); //์ดโญโญโญ
findX = Integer.parseInt(st.nextToken()); //ํโญโญโญ
int size = (int) Math.pow(2, N);
//===============================
//์
๋ ฅ์๋ฃ
partition(0, 0, size);
System.out.println(count-1); //-1 โญโญโญ
}
private static void partition(int startX, int startY, int size) {
if(size <= 2){
findXY(startX, startY);
return;
}
int half = size/2;
boolean left = startX <= findX && findX < startX + half;
boolean right = startX + half <= findX && findX < startX + size;
boolean top = startY <= findY && findY < startY + half;
boolean bottom = startY + half <= findY && findY < startY + size;
if(left && top){
partition(startX, startY, half);
}else if(right && top){
count = count + ((half * half) * 1);
partition(startX+half, startY, half);
}else if(left && bottom){
count = count + ((half * half) * 2);
partition(startX, startY+half, half);
}else if(right && bottom){
count = count + ((half * half) * 3);
partition(startX+half, startY+half, half);
}
}
private static boolean findXY(int startX, int startY){
//Z ๋ฐฉํฅ์ผ๋ก ํ์ธ
for (int j = startY; j < startY + 2; j++) { //Y๊ฐ ๋จผ์
for (int i = startX; i < startX+2; i++) {
count++;
if (i == findX && j == findY) {
return true;
}
}
}
return false;
}
}
'๐ฏ Coding Test' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 1932๋ฒ ์ ์ ์ผ๊ฐํ ์๋ฐ DP (0) | 2022.04.04 |
---|---|
[๋ฐฑ์ค] 9095๋ฒ 1, 2, 3 ๋ํ๊ธฐ ์๋ฐ DP (0) | 2022.03.25 |
[๋ฐฑ์ค] 2630๋ฒ ์์ข ์ด ๋ง๋ค๊ธฐ ์๋ฐ (๋ถํ ์ ๋ณต) (0) | 2022.02.22 |
[๋ฐฑ์ค] 1012 ์ ๊ธฐ๋๋ฐฐ์ถ ์๋ฐ BFS, DFS (0) | 2022.02.21 |
[๋ฐฑ์ค] 1697 ์จ๋ฐ๊ผญ์ง 1์ฐจ์ BFS (0) | 2022.02.12 |