백준 31923 - 마라탕후루 (파이썬)

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

풀이

이 문제는 두 개의 리스트 A와 B를 주어진 연산을 통해 같게 만들 수 있는지를 판별하고, 가능하면 각 원소를 변환하는 횟수를 출력하는 문제이다.

입력 설명

• N : 배열의 길이
• P, Q : 변환 연산에서 사용할 두 개의 숫자
• A : 초기 배열
• B : 목표 배열

연산 규칙

• 각 인덱스 i에서 A[i]에 (Q - P)의 배수를 더하거나 빼서 B[i]로 만들 수 있는지를 확인해야 한다.

---

풀이 과정

1. P와 Q가 같은 경우
   1. 이 경우 (Q - P) = 0이므로 변환이 불가능하다.
   2. 따라서 A와 B가 이미 같은지 확인 후 같다면 YES와 함께 변환 횟수 0을 출력하고, 다르면 NO를 출력한다.
2. P와 Q가 다른 경우 (P < Q로 정렬)
   1. P > Q라면 두 값을 바꾸고 A와 B를 서로 맞바꾼다.
   2. 이렇게 하면 항상 Q - P > 0을 유지할 수 있다.
3. 각 인덱스별로 변환 가능 여부 확인
   1. A[i] == B[i]라면 변환할 필요가 없으므로 0을 저장.
   2. A[i] > B[i]일 때 (A[i] - B[i]) % (Q - P) == 0을 만족하면 변환이 가능하며, 그 몫을 정답 리스트에 저장.
   3. 위 조건이 맞지 않거나 A[i] < B[i]이면 변환이 불가능하므로 NO를 출력.

출력

• 가능한 경우 YES와 변환 횟수 출력.
• 불가능한 경우 NO 출력.

---

시간 복잡도 분석

• O(N): 배열을 한 번 순회하며 조건을 확인하는 과정이므로 N에 비례하는 시간 복잡도를 가진다.

---

코드

# 백준 31923 - 마라탕후루
# 브루트포스

N, P, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if P == Q :
    possible = True
    for i in range(N) :
        if A[i] != B[i] :
            possible = False
            break
    
    if possible :
        print("YES")
        for i in range(N) :
            print(0, end = " ")
    else :
        print("NO")
else :
    if P > Q :
        P, Q = Q, P
        for i in range(N) :
            A[i], B[i] = B[i], A[i]
    
    # P < Q
    possible = True
    answer = []
    for i in range(N) :
        if A[i] == B[i] :
            answer.append(0)
        elif A[i] > B[i] :
            if (A[i] - B[i]) % (Q - P) == 0 :
                answer.append((A[i] - B[i]) // (Q - P))
            else :
                possible = False
                break
        else :
            possible = False
            break

    if possible :
        print("YES")
        for i in range(N) :
            print(answer[i], end = " ")
    else :
        print("NO")