-
[๋ฐฑ์ค(BOJ) 11729๋ฒ] ํ๋ ธ์ด ํ ์ด๋ ์์ (C++)PS(Problem Solving)/C++ 2022. 1. 31. 14:42๋ฐ์ํ
๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/11729
๋ฌธ์ ์ ๋ณด
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ฒซ ๋ฒ์งธ ์ฅ๋์ ์์ธ ์ํ์ ๊ฐ์ N (1 ≤ N ≤ 20)์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
๋ ๋ฒ์งธ ์ค๋ถํฐ ์ํ ๊ณผ์ ์ ์ถ๋ ฅํ๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ K๊ฐ์ ์ค์ ๊ฑธ์ณ ๋ ์ ์ A B๋ฅผ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ถ๋ ฅํ๋๋ฐ, ์ด๋ A๋ฒ์งธ ํ์ ๊ฐ์ฅ ์์ ์๋ ์ํ์ B๋ฒ์งธ ํ์ ๊ฐ์ฅ ์๋ก ์ฎ๊ธด๋ค๋ ๋ป์ด๋ค.
ํ์ด
์ฌ๊ท๋ฅผ ์ด์ฉํด์ ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ์ฌ๊ท๋ฅผ ๊ณต๋ถํ ๋ ๊ท๋ฉ์ ์ฌ๊ณ ๋ฅผ ํตํด์ ํด๊ฒฐํ๋ผ๋ ๋ง์ด ์๋ค. n-1๊ฐ์ ์ํ์ 2๋ฒ ์ผ๋ก ๋ชจ๋ ์ฎ๊ธด ํ, n๋ฒ ์ํ์ 3๋ฒ์ผ๋ก ์ฎ๊ธฐ๊ณ , 2๋ฒ์ผ๋ก ์ฎ๊ฒผ๋ n-1๊ฐ์ ์ํ์ 3๋ฒ์ผ๋ก ์ฎ๊ธฐ๋ฉด ๋๋ค.
์์ค ์ฝ๋
#include <bits/stdc++.h> using namespace std; void func(int a, int b, int n) { if (n == 1) { cout << a << ' ' << b << '\n'; return; } func(a, 6 - a - b, n - 1); // n - 1๊ฐ ์ํ์ ๊ธฐ๋ฅ 1์์ ๊ธฐ๋ฅ 2๋ก ์ฎ๊ธฐ์. cout << a << ' ' << b << '\n'; // n๋ฒ ์ํ์ ๊ธฐ๋ฅ 1์์ ๊ธฐ๋ฅ 3์ผ๋ก ์ฎ๊ธฐ์. func(6 - a - b, b, n - 1); // n -1๊ฐ ์ํ์ ๊ธฐ๋ฅ 2์์ ๊ธฐ๋ฅ 3์ผ๋ก ์ฎ๊ธฐ์. } int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; cout << (1 << n) - 1 << '\n'; // 2^n - 1 func(1, 3, n); return 0; }
๋ฐ์ํ