[BOJ] 백준 12971번 Python

백준 12971번 Python

https://www.acmicpc.net/problem/12971

 

문제

---

준서는 얼마 전 나머지연산에 대해 배웠다.

양의 정수 N을 다른 양의 정수 M으로 나눈 나머지는 항상 0이상 M-1이하의 정수가 된다는 사실이 신기한 준서는 혼자만의 숫자놀이를 고안했다.

먼저 준서는 양의 정수 X1, X2, X3 3개를 임의로 고른다.

그 후 3개의 양의 정수 P1, P2, P3을 고르는데, P1 > X1, P2 > X2, P3 > X3을 만족하도록 고른다.

준서가 알고 싶은 것은 아래의 조건을 만족하는 가장 작은 양의 정수 N이다.

N을 P1로 나눈 나머지가 X1, P2로 나눈 나머지가 X2, P3로 나눈 나머지가 X3

준서가 선택한 P1, P2, P3, X1, X2, X3가 주어졌을 때, 가장 작은 정수 N을 찾는 프로그램을 작성하시오.

 

 

입력

---

공백으로 구분된 6개의 정수 P1, P2, P3, X1, X2, X3가 순서대로 주어진다. 모든 숫자는 1과 300사이의 정수다.

 

 

출력

---

한 줄에 가장 작은 양의 정수 N을 출력한다.

단, 조건을 만족하는 1,000,000,000미만의 양의 정수가 없을 경우 -1을 출력한다.

 

반응형

풀이

---

import sys
input = sys.stdin.readline


def solved():
    P1, P2, P3, X1, X2, X3 = map(int, input().rstrip().split())
    for N in range(X1, P1*P2*P3+1, P1):
        if (N%P2 == X2 and N%P3 == X3):
            return N
    return -1

print(solved())

728x90

브루트 포스로 문제를 풀엇다.

 

최소공배수로 풀어야 할 것 같은 마음에 유클리드 호제법을 이리저리 써봤다.

 

하지만 전탐색으로 문제를 푸니 바로 풀렸다.

 

조금이라도 효율적으로 문제를 풀기 위해 반복문에서 변수가 P1식 증가하도록 했다.

 

P1의 숫자가 클수록 1씩 증가하며 풀이하는 것보다 보다 빠른 수행속도를 보여준다.

 

P1, P2, P3를 비교하여 가장 큰 숫자를 증가량으로 설정하는 것도 방법이다.

 

다만 정수론, 중국인의 나머지 정리를 이용하여 푸는 방법도 추후에 풀어보면 좋을 것 같다.