백준 그리디 문제입니다.
문제
https://www.acmicpc.net/problem/10610
그리디 문제입니다. 주어진 수에서 숫자를 조합하여 30의 배수를 갖는 최댓값을 구하는 문제였습니다. 빠르게 최댓값을 찾기 위해 내림차순 정렬하는 데까지 도달했지만 모든 경우의 수를 구하기엔 N은 10^5까지 주어지기에 시간초과가 날 것이라고 생각했습니다.🐦🐦🐦
다른 해법이 떠오르지 않아 다른 풀이들을 참고하였고 3의 배수임을 알기 위한 공식을 활용한 풀이를 볼 수 있었습니다.
30의 배수를 구하기 위한 조건으로
을 통해 쉽게 해결할 수 있었습니다.
[나의 풀이]
N = str(input())
ans = -1
nums = list(N)
# 정렬했기 때문에 0이 있다면 이미 맨끝
nums = sorted(nums,reverse=True)
# 30의 배수
# 3의 배수 : 모든 수의 합이 3의 배수
# 10의 배수 : 끝자리가 0
if '0' not in nums:
print(-1)
else:
n_sum = 0
for i in range(len(nums)):
n_sum += int(nums[i])
if n_sum%3 == 0:
print("".join(nums))
else:
print(-1)
[다른 사람의 풀이1]
n = str(input())
nums = list(map(int, n))
if sum(nums) % 3 == 0:
nums.sort(reverse=True)
if nums[-1] == 0:
print(''.join(list(map(str, nums))))
else:
print(-1)
else:
print(-1)
[다른 사람의 풀이2]
n = input()
if "0" not in n:
print(-1)
else:
num_sum = 0
for i in range(len(n)):
num_sum += int(n[i])
if num_sum % 3 != 0:
print(-1)
else:
sorted_num = sorted(n, reverse=True)
answer = "".join(sorted_num)
print(answer)
다른 풀이에서도 30의 배수에 해당하는 두 조건을 활용한 풀이였으며 정렬을 언제하는지에 대한 순서만 달랐습니다.🐤🐤🐤
감사합니다.