[백준] 6064, 7568 - Python3

7568. 덩치

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

내 풀이 - 성공

from sys import stdin

N = int(stdin.readline())
people = []
rank = [1] * N

for i in range(N):
    x, y = map(int, stdin.readline().split())
    people.append((x, y))

for i in range(N):
    for j in range(i+1, N):
        if people[i][0] > people[j][0] and people[i][1] > people[j][1]:
            rank[j] += 1
        elif people[i][0] < people[j][0] and people[i][1] < people[j][1]:
            rank[i] += 1

for r in rank:
    print(r, end=" ")

(x, y) 의 형태로 people 에 모두 저장

이중 for 문으로 모든 사람끼리 비교해서
i 의 덩치가 더 크면 rank[i] + 1
j 의 덩치가 더 크면 rank[j] + 1
비교할 수 없으면 그냥 지나가도록 함

그러면 순위가 완성된다

---

6064. 카잉 달력

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

내 풀이 - 성공 (PyPy3)

from sys import stdin

T = int(stdin.readline())

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

for i in range(T):
    M, N, x, y = map(int, stdin.readline().split())
    a, b = x, y
    lcm = M*N // gcd(M, N)
    while a != b:
        if a < b:
            a += M
        else:
            b += N
        if a > lcm or b > lcm:
            a = -1
            break
    print(a)

x, y 는 결국 M, N 의 나머지 값이라는 점을 생각

하지만 몫은 모르는거니까 x, y 에 각각 M, N 을 더해가면서 값이 같아지는 순간을 찾음

ex) 3, 9 => 33 번째
3 + 10 (13) > 9
13 < 9 + 12 (21)
13 + 10 (23) > 21
23 < 21 + 12 (33)
23 + 10 (33) == 33

이 때, a, b 는 최대 M, N 의 최소공배수 (lcm) 까지의 범위로 제한
=> 최소공배수 = M*N // 최대공약수 (gcd)
넘어가면 -1 print

다른 사람의 풀이

from sys import stdin

T = int(stdin.readline())

for i in range(T):
    M, N, x, y = map(int, stdin.readline().split())
    ans = -1
    while(x <= M*N):
        if (x-y) % N == 0:	# if x % N == y % N:
            ans = x
            break
        x += M
    print(ans)

굳이 최소공배수를 구할 필요 없이 넉넉하게 M * N 까지 봐줘도 됨

그리고 x, y 둘 다 생각할 필요 없이 x 에만 M 을 더해가면 된다
=> x - y 를 N 으로 나눈 나머지가 0 이 되면 됨