매일 문제를 꾸준히 풀고 있지만, 블로그에 남기기엔 너무나 쉬운 문제들을 탐내고 있기에… 가끔 문제 풀이를 정리 겸 기록 중입니다.

오늘 풀어본 문제는 solved.ac Sliver 1 난이도의 정렬 문제입니다. 풀이 자체는 그리 어렵지 않아 실제 난이도에 비해 다소 높게 측정된 느낌도 듭니다. (이럴 땐 난이도 기여를 해주어야겠지요. ㅎㅎ Sliver 3 로 의견을 냈습니다.)

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

간단한 정렬 문제 + 최대 공약수 구하기 문제가 합쳐진 문제로 이해하면 될 것 같습니다.

문제 풀이의 step은 다음과 같습니다.

1. 설탕무게 / 총무게 기준으로 입력받은 데이터를 정렬한다.
2. 목표무게량 까지 설탕무게를 누적한다.
3. 전체 설탕 무게를 적절히 분수로 나타내며, 최대공약수를 구해 기약분수꼴로 나타낸다.

정렬은 파이썬의 기본 정렬을 사용하였습니다. sort의 key라는 파라미터 사용법을 잘 습득해두면, 여러 복잡한 정렬에 대해서도 빠르게 적용할 수 있는 좋은 함수입니다. 특히 lambda 함수를 잘 활용해야 sort의 장점이 극대화 되는 것 같습니다. sort 함수와 lambda 함수를 잘 조합한 예제가 아래 블로그에 소개되어 있어 첨부해봅니다.

https://kingofbackend.tistory.com/98

# 설탕무게 / 총무게 기준으로 내림차순 정렬
juice.sort(key=lambda x: [-(x[1] / x[0])])

최대 공약수는 유클리드호제법을 이용하여 구할 수 있습니다.

쉽게 표현하면,

1. a, b 라는 두 정수가 있다.
2. a 는 b보다 크다
3. a 와 b의 최대 공약수는 b와 (a를 b로 나눈 나머지)의 최대 공약수와 같다.

입니다. 구현은 재귀적으로도 할 수 있고, 반복문을 통해서 구현할 수도 있지만, 저는 재귀적으로 구현해보았습니다.

# 최대 공약수 구하는 함수
def gcd(x: int, y: int):
    if x % y == 0: # 탈출 조건 : 나머지가 0인 경우
        return y
    else:
        return gcd(y, x % y)

최대 공약수를 구했다면 분자와 분모를 적절히 연산하여 답을 도출해낼 수 있습니다.

아래는 전체 코드입니다.

def gcd(x: int, y: int):
    if x % y == 0:
        return y
    else:
        return gcd(y, x % y)


n, m = list(map(int, input().split()))

juice = list()
for i in range(n):
    juice.append(list(map(int, input().split())))

# print(juice)

juice.sort(key=lambda x: [-(x[1] / x[0])])

# print(juice)

a = 0
b = 1

M = 0
idx = 0

while M + juice[idx][0] < m:
    M += juice[idx][0]
    a += juice[idx][1]
    idx += 1

b = juice[idx][0]
a *= b

a += juice[idx][1] * (m - M)

# print(a, b)

c = gcd(a, b)

print(str(a // c) + "/" + str(b // c))

이번 달은 아쉽게 하루를 빠뜨렸습니다. ( 회식이 있어서 출근 전에 풀었어야 하는데 깜빡했네요. ㅠㅠ ) 그래도 포기하지 않고 꾸준히! 정진해 나가야겠습니다. 물론 간간히 어려운 문제를 풀어 느슨해진 제 스스로에게 기강을 잡을 필요도 있겠습니다.