[Baekjoon/백준] 1629번 Python

문제 출처: www.acmicpc.net/problem/1629

1629번: 곱셈

 

1. 문제 접근 방식

- 문제만 보면 정말 간단해 보이지만 보이는게 다가 아니다. 문제를 따라가면서 코딩을 하면 어김없이 시간초과가 나기 때문이다. 두가지 방법을 생각해보았다. 파이썬에서 기본적으로 제공하는 함수인 pow를 이용하거나 재귀를 이용하는 방식이다. 

 

2. 내가 푼 코드

import sys

A, B, C = map(int, sys.stdin.readline().split())

# pow(A, B, C) = A의 B승을 C로 나눈 나머지
print(pow(A, B, C))

import sys

A, B, C = map(int, sys.stdin.readline().split())

# 재귀의 방식을 사용하기 위해 함수로 작성
# B가 1일 경우는 그냥 나누기 진행
# 이외의 경우는 재귀의 방식을 이용하여 코드 작성
def solve(A, B):
    if B == 1:
        return A % C
    else:
        n = solve(A, B // 2)
        if B % 2 == 0:
            return n * n % C
        else:
            return n * A % C


print(solve(A, B))

 

3. 결과 및 느낀점

- 성공! 재귀의 방식에 대해 다시 한번 공부도 하고 파이썬 함수에 대해서도 공부할 수 있는 좋은 문제였다.