[C++] 백준(BOJ) - 1629 : 곱셈

14 Jun 2023 in Develop on C++, Algorithm Last modified at: 2024-05-25

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 1629 : 곱셈(링크)

알고리즘

1. 수학 - 모듈러 연산
2. 분할정복
3. 재귀

풀이

• A를 B만큼 곱하였을 때, 스택 오버플로우가 난다는 것을 확인한 후 모듈러 연산을 통해 크기를 줄여야 한다는 것을 떠올리기

모듈러 연산
(a * b) % c = ((a % c) * (b % c)) % c
(a + b) % c = ((a % c) + (b % c)) % c

• B만큼 반복한다는 for문을 사용하여 문제를 풀 경우 시간 복잡도에 걸리는 것을 확인 -> 분할 정복법을 이용해 재귀적으로 문제를 풀어나갈 생각을 해야 함

for(int i= 0 -> b) // 20억 * 20억 => 시간복잡도 초과 (틀린 풀이)

• b가 짝수인 경우와 홀수인 경우로 나눠서 A^B 재귀함수 리턴 값 따로 처리 해주기

코드

// BOJ - 1629 : 곱셈
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // typedef 키워드로 기존 자료형에 내가 원하는 별칭을 부여할 수 있다

ll a, b, c;

ll go(ll a, ll b)
{
    if (b == 1) return a % c;
    ll res = go(a, b / 2);
    res = (res * res) % c;

    // b가 홀수 일때, a를 한번 더 곱해준다
    if (b % 2) res = (res * a) % c;
    return res;
}

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

    cin >> a >> b >> c;

    // top-down 형식의 재귀 함수로 문제 풀이 접근
    cout << go(a, b) << '\n';

    return 0;
}

평가

• 분할정복의 가장 기초가 되는 문제 - 프로그래머스의 콜라 문제와 유사한 것으로 생각됨
• 짧고 간단한 문제이지만 수학(모듈러연산), 재귀, 시간복잡도 등 코테에서 센스있게 고려해야할 부분들이 많이 있는 문제이므로 이러한 문제들을 자주 풀어보며 연습할 필요가 있다

참고 : 풀이-GitHub링크