[알고리즘/그리디] 백준 BOJ 10610 30

8. BOJ 10610 30

10610번: 30

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

예제 입력 1

30

예제 출력 1

30

예제 입력 2

102

예제 출력 2

210

예제 입력 3

2931

예제 출력 3

-1

예제 입력 4

80875542

예제 출력 4

88755420

 

 

---

💡나의 문제 풀이

문제 이해

• 0으로 시작을 하지 않는 수이다.
• 30의 배수가 되어야 한다. (30에 대한 소인수 분해)

 

문제 해결 아이디어

• 이 수에 포함된 숫자들을 섞자 → 문자열로 입력 받아 각각의 수를 리스트로 넣으면 되겠다.
• 30을 소인수 분해 → 30 = 2 * 3 * 6
  • 숫자들을 각각 섞어 그 수가 (236)을 인수로 가지면 된다.
  • M = (236) * k= 30 * k (이때, k는 1 이상의 양의 정수)
• 그리디로 푸는 것이 정당한가?
  • 최대 105개의 숫자로 구성될 수 있다고 하면, 맨 앞자리에 올 수 있는 경우의 수는 105, 그다음은 104… → 105x104x103x…2x1 (경우의 수가 너무 크다..!)

---

고려 사항

• 먼저 고려해야 할 사항들
  1. 30의 배수이므로, 가장 마지막에 오는 수는 0이어야 한다.
  2. 3의 배수는 3, 6, 9, 12, 15 ,… 로 각 자리의 합을 더하면 무조건 3의 배수이다. 따라서 모든 수의 합이 3의 배수인지도 확인해야 한다.
• 30의 배수 조건을 찾아보니 1) 3의 배수이면서 2) 일의 자리가 0인 수라고 한다. 따라서 위 조건만 만족하는 수를 출력해보도록 한다.
• 여기서 더 필요한 조건은 없을까? 고민해보았다.
  • 예제 입력 2인 102에 대하여, 예제 출력 2는 210을 출력하였다. 120을 출력할 수도 있었는데 210을 출력했다.. 왜일까?
  • → 조건을 다시 한번 읽어보니, 만들 수 있는 ‘가장 큰 수’ 라고 한다. 그렇다면 리스트를 내림차순으로 정렬하면 되겠다!

---

작성 코드

N = list(map(int, input())) # 0으로 시작 X
sum = 0

# 1) 0을 포함하고 있는가?
if 0 not in N:
  print('-1')

# 2) 각 자리의 모든 합이 3의 배수인가?
for n in N:
  sum += n;
if sum%3 !=0:
  print('-1')

N.sort(reverse=True)
for n in N:
  print(n, end='')

• 출력 초과 발생..
• 함수 작성 가능할까? → 맞았다 😊

N = list(map(int, input())) # 0으로 시작 X

def func():
  sum = 0
  flag = 0
  for n in N:
    sum += n;
    if n==0: 
      flag = 1
	# 0 발견하지 못하거나 전체 자리의 합이 3의 배수가 아닌 경우
  if flag==0 or sum%3 !=0:
    return -1

if func() == -1:
  print('-1')
else:
  N.sort(reverse=True)
  for n in N:
    print(n, end='')

 

---

 

답안 코드

• 아래 답안을 작성한 분은 조건을 확인도 하기 전에 sorted() 함수를 사용했다.
• 각 반복문을 돌 때마다 join() 함수를 이용해 출력할 수 있도록 구현했다.

n = input()
n = sorted(n, reverse=True)
sum = 0
if '0' not in n:	# 우선은 input의 디폴트인 string으로 받았기에 '0' 문자로 적음
    print(-1)
else:
    for i in n:
        sum += int(i)
    if sum % 3 != 0 :	# 3의 배수 체크
        print(-1)
    else :
        print(''.join(n))

 

---

리뷰 및 점검

• 파이썬의 sum() 함수 → 리스트 객체에 사용하지 못했는데 아직 명확한 이유는 찾지 못했다 ☹️ 취약점이 있다고 하니, 그냥 직접 코드로 작성하는 수 밖에!
• [python] 파이썬 sum함수 정리와 예제
• 30의 배수에 대해서 잘 이해하고 분석해서 쉽게 풀린 문제이다!
• 다만 함수로 작성한 것이 약간 아쉽다.