๐ ๋ฌธ์ ์ค๋ช
ํ์๋ ํฌ๊ธฐ๊ฐ 2N × 2N์ธ 2์ฐจ์ ๋ฐฐ์ด์ Z๋ชจ์์ผ๋ก ํ์ํ๋ ค๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, 2×2๋ฐฐ์ด์ ์ผ์ชฝ ์์นธ, ์ค๋ฅธ์ชฝ ์์นธ, ์ผ์ชฝ ์๋์นธ, ์ค๋ฅธ์ชฝ ์๋์นธ ์์๋๋ก ๋ฐฉ๋ฌธํ๋ฉด Z๋ชจ์์ด๋ค.
N > 1์ธ ๊ฒฝ์ฐ, ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ 2 ^ N-1 × 2 ^ N-1๋ก 4๋ฑ๋ถ ํ ํ์ ์ฌ๊ท์ ์ผ๋ก ์์๋๋ก ๋ฐฉ๋ฌธํ๋ค.
๋ค์ ์๋ 2^2 × 2^2 ํฌ๊ธฐ์ ๋ฐฐ์ด์ ๋ฐฉ๋ฌธํ ์์์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ค์์ N=3์ผ ๋์ ์์ด๋ค.
๐ ์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ N, r, c๊ฐ ์ฃผ์ด์ง๋ค.
๐ ์ถ๋ ฅ
rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ค.
๐ซ ์ ํ์ฌํญ
- 1 ≤ N ≤ 15
- 0 ≤ r, c < 2N
- ์๊ฐ์ ํ : 0.5 s
โค๏ธ ๋ฌธ์ ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ while ๋ฐ๋ณต๋ฌธ
๊ฐ ๊ฐ๋ก์ ์ธ๋ก์ n์ 2๋ก ๋๋๋ฉด, 4๋ถ๋ฉด์ด ๋ง๋ค์ด์ง๋ค.
์ด๋, 4๋ถ๋ฉด ๊ธฐ๋ฐ์ผ๋ก r์ด 2 ^ n/2๋ณด๋ค ํฌ๋ฉด 3, 4๋ถ๋ฉด์ ํด๋นํ๋ค.
c์ด 2 ^ n/2๋ณด๋ค ํฌ๋ฉด, 2, 4๋ถ๋ฉด์ ํด๋นํ๋ค.
3, 4๋ถ๋ฉด์ธ ๊ฒฝ์ฐ์๋ 1, 2๋ถ๋ฉด๋งํผ ์์๋ฅผ ๋ํด์ฃผ๋ฉด ๋๋ค. ์ด๋ฅผ ๊ณ์ฐํ๋ ๋ฐฉ๋ฒ์ 2 ^ n * 2 ^ (n - 1).
2, 4๋ถ๋ฉด์ธ ๊ฒฝ์ฐ์๋ r์์ ์ด๋ฏธ 4๋ถ๋ฉด์ธ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํด์คฌ๊ธฐ ๋๋ฌธ์, 1๋ถ๋ฉด์ธ ๊ฒฝ์ฐ๋ง ๋ํด์ฃผ๋ฉด ๋๋ค. (1 / 4์ฌ๋ถ๋ฉด)
์ด๋ฅผ ๊ณ์ฐํ๋ ๋ฐฉ๋ฒ์ 2 ^ (n - 1) * 2 * (n - 1).
n ์ด 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ๊ฒฝ์ฐ์ ์ด ๊ณ์ฐ์ ๋ฐ๋ณตํด๊ฐ๋ฉด์, n์ 1์ฉ ๋นผ์ค๋ค.
let fs = require("fs");
let [n, r, c] = fs
.readFileSync(0, "utf8")
.trim()
.split(" ")
.map(Number);
function solution(n, r, c) {
let visitedCount = 0;
while (n >= 1) {
// ํ์ฌ n์ ๊ธฐ์ค์ผ๋ก 4์ฌ๋ถ๋ฉด์ ๊ทธ๋ ค ํฐ ๊ฒฝ์ฐ
if (r >= 2 ** (n - 1)) {
visitedCount += 2 ** (2 * n - 1);
r %= 2 ** (n - 1);
}
if (c >= 2 ** (n - 1)) {
visitedCount += 2 ** (2 * n - 2);
c %= 2 ** (n - 1);
}
n--;
}
return visitedCount;
}
console.log(solution(n, r, c));
์๊ฐ ๋ณต์ก๋๋ n๋ถํฐ 1๊น์ง ๋ฐ๋ณตํ๊ฒ ๋๋ฏ๋ก O(n)์ด๋ค.
2๏ธโฃ ๋นํธ ์ฐ์ฐ์
2 ^ n ๋ฌธ์ ์ธ ๊ฒ์ ๋ณด์๋ง์ ๋นํธ ์ฐ์ฐ์ผ๋ก ํ ์ ์์ ๊ฒ์ด๋ผ๊ณ ์๊ฐํ๋ค.
๊ทธ๋ฐ๋ฐ ์์ง ๋นํธ์ฐ์ฐ์ ์ต์ํ์ง ์์ ์ด์๋ก ๋นํธ์ฐ์ฐ์๋ฅผ ๊ณต๋ถํ๋ฉด์ ๋ฌธ์ ๋ฅผ ํ์๋ค.
let fs = require("fs");
// ํ์ผ์์ ์
๋ ฅ๊ฐ์ ์ฝ์ด์ ์ซ์๋ก ๋ณํ (n: ํ๋ ฌ ํฌ๊ธฐ ์ง์, r: ํ ์ธ๋ฑ์ค, c: ์ด ์ธ๋ฑ์ค)
let [n, r, c] = fs.readFileSync("test.txt", "utf8").trim().split(" ").map(Number);
function solution(n, r, c) {
let order = 0; // ๋ฐฉ๋ฌธ ์์๋ฅผ ์ ์ฅํ๋ ๋ณ์
// ํฐ ํ๋ ฌ(2^n × 2^n)์ ์์ ๋จ์(2×2)๊น์ง ์ชผ๊ฐ๋ฉด์ ํ์
for (let i = n - 1; i >= 0; i--) {
/**
* (r >> i) & 1 : r์ i๋ฒ์งธ ๋นํธ๋ฅผ ์ถ์ถ
* r >> i : r์ i๋นํธ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ (์ฆ, i๋ฒ์งธ ๋นํธ๊ฐ ๋งจ ์ค๋ฅธ์ชฝ์ ์์น)
* & 1 : ๋งจ ์ค๋ฅธ์ชฝ ๋นํธ๋ง ๋จ๊ธฐ๊ณ ๋๋จธ์ง๋ 0์ผ๋ก ์ค์ (๋นํธ ๋ง์คํน)
*/
let rowBit = (r >> i) & 1; // r์ i๋ฒ์งธ ๋นํธ ์ถ์ถ → ํ์ฌ ํ์ ์ฌ๋ถ๋ฉด ์ ๋ณด
/**
* (c >> i) & 1 : c์ i๋ฒ์งธ ๋นํธ๋ฅผ ์ถ์ถ
* ์๋ฆฌ๋ r๊ณผ ๋์ผํ๋ฉฐ, ํ์ฌ ์ด์ด ์ด๋ ์ฌ๋ถ๋ฉด์ธ์ง ํ์ธํ๋ ์ญํ
*/
let colBit = (c >> i) & 1; // c์ i๋ฒ์งธ ๋นํธ ์ถ์ถ → ํ์ฌ ์ด์ ์ฌ๋ถ๋ฉด ์ ๋ณด
/**
* ํ์ฌ ์ฌ๋ถ๋ฉด์ ์์ ๊ณ์ฐ
* rowBit * 2 + colBit : 4๊ฐ์ ์ฌ๋ถ๋ฉด ์ค ๋ช ๋ฒ์งธ์ธ์ง ํ๋ณ
* - (0,0) → 1์ฌ๋ถ๋ฉด (์ข์) → 0
* - (0,1) → 2์ฌ๋ถ๋ฉด (์ฐ์) → 1
* - (1,0) → 3์ฌ๋ถ๋ฉด (์ขํ) → 2
* - (1,1) → 4์ฌ๋ถ๋ฉด (์ฐํ) → 3
*
* (1 << (2 * i)) : 2^2i ๋ฅผ ๊ณ์ฐํ์ฌ ํ์ฌ ํ๋ ฌ ํฌ๊ธฐ์ ๋ง๊ฒ ์ด๋
* - i = 2 → (1 << 4) = 16
* - i = 1 → (1 << 2) = 4
* - i = 0 → (1 << 0) = 1
*
* ๋ฐ๋ผ์ ํ์ฌ ์ฌ๋ถ๋ฉด์ ํฌ๊ธฐ๋งํผ ์ด๋ํ์ฌ order๋ฅผ ์
๋ฐ์ดํธํจ.
*/
order += (rowBit * 2 + colBit) * (1 << (2 * i));
}
return order; // ์ต์ข
๋ฐฉ๋ฌธ ์์ ๋ฐํ
}
console.log(solution(n, r, c)); // ๊ฒฐ๊ณผ ์ถ๋ ฅ
chat gptํํ ์ฃผ์์ ์จ๋ฌ๋ผ๊ณ ๋ถํํ๋๋ ์ด์ฌํ ์จ์คฌ๋ค.
๋ฌธ์ ํ์ด์์ ๋ ๊ฐ์ ํ ๋ถ๋ถ ์์ผ๋ฉด ๋๊ธ๋ก ๋จ๊ฒจ์ฃผ์๋ฉด ๊ฐ์ฌํ๊ฒ ์ต๋๋ค.
'๐ algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] ๋ฌธ์์ด ๊ฒ์ 2 - JavaScript ํ์ด (0) | 2025.02.14 |
---|---|
[๋ฐฑ์ค] ์ต์๋น์ฉ ๊ตฌํ๊ธฐ (0) | 2025.02.13 |
[๋ฐฑ์ค] ๋น๋ฌผ - JavaScript ํ์ด (0) | 2025.02.11 |
[์๊ณ ๋ฆฌ์ฆ] ๋ฐฑ์ค 2447 ๋ณ์ฐ๊ธฐ - 10 JAVA ๋ฌธ์ ํ์ด (2) | 2024.03.24 |
[Algorithm] ๋ณํฉ์ ๋ ฌ์ ๋ํด ์์๋ณด์ !! ๐ (0) | 2024.03.21 |