๐ฃ
Baekjoon์์ PASS๋ ์ฝ๋๋ง ์
๋ฐ์ดํธํฉ๋๋ค.
์๊ณ ๋ฆฌ์ฆ์ ๋จผ์ ํ์ดํ๋ ์ธ์ด(Java)๊ฐ ์ ํด์ ธ์์ด,
ํ์ด ์ธ์ด(Python, C++, Java)๊ฐ ๋ชจ๋ ์
๋ฐ์ดํธ๋ ๋๊น์ง๋ ์๊ฐ์ด ๊ฑธ๋ฆด ์ ์์ต๋๋ค.
๋ฌธ์
ํ์๋ ํฌ๊ธฐ๊ฐ 2N ร 2N์ธ 2์ฐจ์ ๋ฐฐ์ด์ Z๋ชจ์์ผ๋ก ํ์ํ๋ ค๊ณ ํ๋ค.
์๋ฅผ ๋ค์ด, 2ร2๋ฐฐ์ด์ ์ผ์ชฝ ์์นธ, ์ค๋ฅธ์ชฝ ์์นธ, ์ผ์ชฝ ์๋์นธ, ์ค๋ฅธ์ชฝ ์๋์นธ ์์๋๋ก ๋ฐฉ๋ฌธํ๋ฉด Z๋ชจ์์ด๋ค.
๋ง์ฝ, N > 1์ด ๋ผ์ ์ผ์ชฝ ์์ ์๋ ์นธ์ด ํ๋๊ฐ ์๋๋ผ๋ฉด, ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ 2N-1 ร 2N-1๋ก 4๋ฑ๋ถ ํ ํ์ ์ฌ๊ท์ ์ผ๋ก ์์๋๋ก ๋ฐฉ๋ฌธํ๋ค.
๋ค์ ์๋ 22 ร 22 ํฌ๊ธฐ์ ๋ฐฐ์ด์ ๋ฐฉ๋ฌธํ ์์์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ค์์ N=3์ผ ๋์ ์์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ N, r, c๊ฐ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ค.
์ ํ
์
๋ ฅํ ์ขํ๊ฐ ๋ช๋ฒ์งธ ๋ฐฉ๋ฌธํ๋ ๊ณณ์ธ์ง ์ถ๋ ฅํ๋ ๋ฌธ์ ์
๋๋ค.
๊ฐ ๋ฐฉ์ ๋๋ฌํ๋ ์์ฐจ๊ฐ ์ด๋ค์ง ์ดํด๋ด์ผํฉ๋๋ค.
์ ๊ทผ๋ฐฉ๋ฒ 1 : ์ค์ ๋ก ์ ํด์ง ๊ท์น๋๋ก ๋ฐฉ๋ฌธํ๋ฉด์ ํด๋น r, c์ ๋์ผํด์ง ๋ ํด๋น ์๋ฒ์ ๋ฐํํ๋ค.
์ ๊ทผ๋ฐฉ๋ฒ 2 : ํฌ๊ฒ 4๊ฐ์ง์ ์์ญ์ผ๋ก ๋๋์ด์ง๋ ํน์ง์ ์ฐพ์ ์งํํ๋ค.
์ฒ์ ๋ฌธ์ ๋ฅผ ๋ถ์ํ๋ฉด ์ด๋ ๊ฒ 2๊ฐ์ง์ ๋ฐฉ๋ฒ์ ์๊ฐํ๊ฒ ๋ฉ๋๋ค.
์ฌ์ค ์๊ฐ๋๋ ๋ชจ๋ ๋ฐฉ๋ฒ์ ๊ตฌํํด๋ณด๊ณ ์ํ๋๊ฒ ์ ๊ณต๋ถ๋ฐฉ๋ฒ์ด์ง๋ง,
๋ฐฉ๋ฒ1์ ๊ฒฝ์ฐ๋ ์ฌ์ด์ฆ๊ฐ ์กฐ์ ๋๋ฉด์ ๊ณ์ฐํ๋ ๊ฒ์ด ๋ ์ด๋ ต๊ฒ ๋๊ปด์ก์ต๋๋ค.
๋ฐ๋ผ์ ๋ฐฉ๋ฒ 2๋ฒ์ผ๋ก ํ์ด๋ฅผ ์งํํ์์ต๋๋ค.
์ฐ์ ๊ฐ์ฅ ํฐ ํน์ง์ ๋จผ์ ๋ณด๊ฒ ์ต๋๋ค.
N์ด ์ ํด์ง๋ฉด 2N์ด ์ ํด์ง๊ณ , ๊ทธ๋ผ ํ ๋ณ์ ๊ธธ์ด๊ฐ ๊ธ๋ฐฉ ๊ตฌํด์ง๊ฒ ๋ฉ๋๋ค.
๊ทธ๋ผ ์กฐ๊ธ ์์ธํ๊ฒ ์์๋ณด๊ฒ ์ต๋๋ค.
ํ์ฌ์ ๋ชจ์์ ๊ฐ๊ณ ์๋ Z ๊ณต๊ฐ์ ์ ํฌ๋ ์๊ณ ์์ต๋๋ค.
์ ๊ทผ๋ฐฉ๋ฒ 2์ ๋ด์ฉ๋๋ก ์ฐจ๊ทผ์ฐจ๊ทผ ๊ทธ ๋ฒ์๋ฅผ ์ขํ๋ณด๊ฒ ์ต๋๋ค.
์ ํฌ๋ i=1, j=2์ผ ๋์ 6์ ๊ฐ์ ๊ตฌํด๋ด
์๋ค.
๊ท์น์ ์ฐพ์ ๋, ๊ฐ์ฅ ํฐ ํน์ง์ ๋๋ฌด ํ์ด์ฐ์ง ์๋๊ฒ ์ค์ํ๋ค๊ณ ์๊ฐํฉ๋๋ค.
์ฃผ์ด์ง ๊ฐ, ๊ทธ๋๋ก๋ฅผ ํ๋๊ฒ ๋์ค์ ์ฝ๋๋ก ์ ์ ๋ ํธํ๊ฑฐ ๊ฐ๋๋ผ๊ตฌ์.
์ฒ์์ ๊ฐ์ฅ ์ค์ํ ๊ฒ์ 1~4์ฌ๋ถ๋ฉด์ ๊ฒฝ๊ณ๋ฅผ ์ ํ์ธํด์ ์๋ง๋ ์์ญ์ ๋ค์ด๊ฐ๋ ๊ฒ์
๋๋ค.
ํ์ฌ ์ ํฌ๋ ๊ฐ ์์๊ฐ์ ๊ตฌํ๊ธฐ ์ํด์ ํ ๋ณ์ ๊ฐ๊ณผ ์ฐ๊ฒฐ ์ง์ด๋ณด๊ฒ ์ต๋๋ค
์ง๊ธ์ ๋ถ๋ฅ๋ฅผ ํตํด 2์ฌ๋ถ๋ฉด์ ์ ํฌ๊ฐ ์ํ๋ i=1, j=2์ด ์ํด์์ผ๋,
์ ์์ญ์ผ๋ก ์์ธ๋ฅผ ํ์ธํด๋ด
๋๋ค.
ํ์ฌ์ ์์ญ์์๋ ๊ฐ i, j์ ์๋ฒฝํ๊ฒ ์ผ์นํ๋ ๊ฐ์ด ์๊ฒผ์ต๋๋ค!
๋ ์์ธํ๊ฒ ์์ญ์ ํ์ธํ ํ์๊ฐ ์๊ฒ ์ต๋๋ค.
๊ฒ์ฌ๋ฅผ ๋ฉ์ถ๋ ์กฐ๊ฑด์ i,j๊ฐ ์๋ฒฝํ๊ฒ ์ผ์นํ ๋๋ ์์ง๋ง, ํ ๋ณ์ ๊ธธ์ด๊ฐ 1์ด ๋ ๋๋ผ๊ณ ์๊ฐํด๋ ๋๊ฒ ์ฃ !
์ด ์กฐ๊ฑด์ ๋ณธ์ธ์ด ํธํ๋๋ก ํ์๋ฉด ๋ ๊ฒ ๊ฐ์ต๋๋ค.
์ด๋ฏธ ์ด์ ์ ๊ฐ์ ๊ตฌํ ์ ์๊ธฐ์, ์ง๊ธ ๊ตฌํ๋ ๊ฐ์ ์ค์ฒฉํ๋ ๊ฐ์ผ๋ก ์งํํด๋ณด๊ณ ์ํ๋๋ฐ,
0,1,2,3 ์ ํ์ฌ ์๊ณ ์๋ ๊ฐ๊ณผ ์ฐ๊ด์ง์ด์ผ ํ๋๊ฒ ์ด๋ ต๋ค์.
์ง๊ธ ์๊ณ ์๋ ๊ฑด ํ๋ณ์ ๊ธธ์ด์ ์ฐ๊ด์ง๋๊ฒ ์ ์ผ ์ข์ ๊ฒ๊ฐ์์ ์์ฒ๋ผ ํ๋ณ/2 * ์ฌ๋ถ๋ฉด์ผ๋ก ์ ๋ฆฌํ์ต๋๋ค.
๊ทธ๋ผ ์ด์ ๋จ๊ณ์ ๋ด์ฉ๋ ์์ ์ ํด์ค์ผ๊ฒ ์ฃ .
ํ์ฌ ๊ณ ์น๋ ค๊ณ ๋ณด๋ ํ๋ณ/2 * ์ฌ๋ถ๋ฉด๋ ๋ถ๊ฐ๋ฅ ํฉ๋๋ค.
๊ทธ๋ ๋ค๋ฉด ์กฐ๊ธ ์กฐ์์ ํด๋ณด๋ ค๊ณ ์๊ฐ์ ํด๋ณด๋, ํ๋ณ/2 ํ๋ณ/2 ์ฌ๋ถ๋ฉด์ผ๋ก ํ๋ฉด ๊ฐ๋ฅํ๋ค๋ ์ฌ์ค์ ํ์ธํ ์ ์์ฃ .
์ด๋ ๊ฒ ๋ค์ ๋ค์ ๋จ๊ณ๋ฅผ ์์ ํ๋ฉด, ํ๋ณ/2 ํ๋ณ/2 ์ฌ๋ถ๋ฉด์ผ๋ก ๋ชจ๋ ์ ์ฉ์ด ๊ฐ๋ฅํฉ๋๋ค.
์ด์ ์ด๋ฅผ ์ฝ๋๋ก ์์ฑํ๋ฉด ๋๊ฒ ์ต๋๋ค.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, R, C, NUM;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
N = (int) Math.pow(2, N); // 2^N์ ์ ์ฌ๊ฐํ
search(0, 0, N);
System.out.println(NUM);
}
public static void search(int i, int j, int MAX) {
if (MAX == 1)
return;
if (R < i + MAX / 2 && C < j + MAX / 2) {
search(i, j, MAX / 2);
} else if (R < i + MAX / 2 && C >= j + MAX / 2) {
NUM += MAX/2 * MAX/2;
search(i, j + MAX / 2, MAX / 2);
} else if (R >= i + MAX / 2 && C < j + MAX / 2) {
NUM += MAX/2 * MAX/2 * 2;
search(i + MAX / 2, j, MAX / 2);
} else {
NUM += MAX/2 * MAX/2 * 3;
search(i + MAX / 2, j + MAX / 2, MAX / 2);
}
}
}