[BOJ/백준] 13116 - 30번 [C++/python]

문제 링크

13116번: 30번

문제 풀이

이 문제는 두 수 a, b의 공통 부모 중 최댓값을 찾는 문제이다. 이 문제의 경우 최댓값을 다음과 같이 찾을 수 있었다.
a, b를 각각 33, 79라고 한다면 두 수의 부모 배열은 각각의 수를 2로 나눠가면서 구할 수 있다.

• 33 : [16, 8, 4, 2, 1]
• 79 : [39, 19, 9, 4, 2, 1]

두 부모의 배열을 구했다면, 두 수의 공통된 최대 부모 값이 4임을 알 수 있다.

정답 코드

C++

// 30번
// https://www.acmicpc.net/problem/13116

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long

int main() {
    fast;
    int T, a, b;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        vector<int> va;
        vector<int> vb;
        if (a > b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        while (a > 0) {
            va.push_back(a);
            a /= 2;
        }
        while (b > 0) {
            vb.push_back(b);
            b /= 2;
        }
        sort(va.begin(), va.end());
        sort(vb.begin(), vb.end());
        int ans = 1;
        for (int i = 0; i < va.size(); i++)
            if (va[i] == vb[i]) ans = va[i];
        cout << ans * 10 << "\n";
    }
}

python

for _ in range(int(input())) :
    a, b = map(int, input().split())
    if a > b : a, b = b, a
    a_lst = []
    b_lst = []
    while a > 0 :
        a_lst.append(a)
        a //= 2
    while b > 0 :
        if b in a_lst :
            print(b * 10)
            break
        b //= 2

파이썬 코드는 C++과 방법이 약간 다른데, C++과 같은 방법을 사용했을때는 시간초과가 났었다. 반복문을 줄이기 위해 a의 부모 배열을 만들어준 뒤, b를 2로 나눠가면서 비교를 동시에 해줬다.