[SWEA] 11688 Calkin-Wilf tree 1

문제

SWEA 11688 : Calkin-Wilf tree 1

SW Expert Academy

접근

 문제의 조건은 크게 두 개인데,

   ∙ 트리의 루트는 1/1 을 나타낸다.
   ∙ 트리의 각 노드는 왼쪽 자식과 오른쪽 자식을 가지는데 어떤 노드가 a/b 를 나타내고 있다면, 왼쪽 자식은 a/a+b 를 오른쪽 자식은 a+b/b 를 나타낸다.

 따라서 입력받은 문자열을 하나씩 확인하며 'L'일 경우 b = a + b를 해주고, 'R'일 경우 a = a + b를 해주면 쉽게 답을 구할 수 있다.

코드

#include <iostream>
#define endl "\n"

using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        string s;
        cin >> s;
        int a = 1, b = 1;
        for (int j = 0; j < s.size(); j++) {
            if (s[j] == 'L')
                b = a + b;
            else
                a = a + b;
        }
        cout << "#" << i << " " << a << " " << b << endl;
    }
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study