BOJ 2685 - 님비합 링크
(2024.03.07 기준 S3)

문제

두 개의 음이 아닌 정수 $X$와 $Y$의 Nim-B-sum ($B$진법 nim sum)을 NimSum (B, X, Y)라고 하자. 이 값은 다음과 같이 계산할 수 있다.

1. $X$와 $Y$를 $B$진법으로 나타낸다.
2. Nim-B sum의 각 자리 수는 $X$와 $Y$의 $B$진법 표기에서의 각 자리의 합을 $B$로 나눈 나머지이다.

$B$, $X$, $Y$가 주어질 때마다 NimSum (B, X, Y)의 10진수 표현을 출력

알고리즘

진법 변환을 구현

풀이

10진수 $N$을 $B$진법으로 나타내려면 $N$을 $B$로 나누면서 나머지를 저장하며 이를 $N$이 0이 될 때까지 반복한다. 그리고 저장된 나머지를 거꾸로 뒤집으면 $B$진법으로 표현된 $N$이 된다.

이를 그대로 $X$와 $Y$에 적용하고 각 자리마다 더해서 $B$로 나누고 10진수로 다시 만들면 되는데, $B$진법으로 표현된 수를 10진수로 만들려면 모든 자리마다 $B^i$를 곱해 모두 더하면 된다. 이때 i는 자리의 순서, 즉 인덱스(0-based index)이다.

위 두 방법을 그대로 구현하면 되는 간단한 문제이다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

// N을 B진법으로 변환. 뒤집지 않고 반환한다.
vector<int> change(int N, int B){
    vector<int> res;
    while (N){
        res.push_back(N % B);
        N /= B;
    }
    return res;
}

int NimSum(int B, int X, int Y){
    if (X < Y) swap(X, Y); // X에 Y를 더하기 위해 길이가 X가 Y보다 같거나 길게 한다.
    vector<int> X_ = change(X, B);
    vector<int> Y_ = change(Y, B);

    for (int i = 0, sz = Y_.size(); i < sz; i++) // Y의 길이만큼 각 자리마다 계산
        X_[i] = (X_[i] + Y_[i]) % B;

    int res = 0, b = 1; // 결과를 10진수 변환
    for (int i = 0, sz = X_.size(); i < sz; i++){
        res += X_[i] * b;
        b *= B;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    for (int B, X, Y; T; T--){
        cin >> B >> X >> Y;
        cout << NimSum(B, X, Y) << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline

# N을 B진법으로 변환. 뒤집지 않고 반환한다.
def change(N, B):
    res = []
    while N:
        N, r = divmod(N, B)
        res.append(r)
    return res

def NimSum(B, X, Y):
    if X < Y: # X에 Y를 더하기 위해 길이가 X가 Y보다 같거나 길게 한다.
        X, Y = Y, X
    X = change(X, B)
    Y = change(Y, B)

    for i in range(len(Y)): # Y의 길이만큼 각 자리마다 계산
        X[i] = (X[i] + Y[i]) % B

    res = 0; b = 1 # 결과를 10진수 변환
    for i in range(len(X)):
        res += X[i] * b
        b *= B
    return res

for _ in range(int(input())):
    B, X, Y = map(int, input().split())
    print(NimSum(B, X, Y))