[백준/파이썬] 30 (10610)

 

처음 본 풀이 방식이라 기억할라고 정리하는 문제~

 

 

📌 풀이 문제

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

10610번: 30

 

 

👩‍💻 풀이방법 1 (틀린 풀이) : 메모리 초과

처음에는 input 받은 숫자를 순열을 사용하여 만들 수 있는 모든 경우의 수로 숫자를 하나하나 만들었다.

그 다음에 만든 숫자를 30으로 나눠보며 나누어 떨어진다면 바로 break 후, 출력 시켰다

<틀린 코드>

from itertools import permutations #순열 사용을 위한 import

n = input()
arr = []
ans = -1
for i in n:  #input 받은 숫자 하나하나 잘라서 arr에 저장
    arr.append(i)
k = list(permutations(arr, len(arr)))	# arr에 저장된 수로 순열 만들기


for i in k:	#순열에 저장된 수 만큼 반복문을 돌며
    if int("".join(i)) % 30 == 0:	#분리 된 수를 붙여 하나의 int 숫자로 만든 뒤 30으로 나누어 떨어진다면
        ans = (int("".join(i)))		#해당 수 출력
        break
print(ans)

 

하지만 메모리 초과로 실패가 떴다

 

그래서 다른 블로그를 참고한 결과 다음과 같이 풀어야함을 이해했다.

 

👩‍💻 풀이방법 2

 

1. 받은 숫자에 0이 없으면 -1

2. 숫자들 합이 3으로 나누어 떨어지지 않으면 -1

3. 위 두 조건을 모두 충족한다면 내림차순 정렬 후 출력

 

n = input()
n = sorted(n, reverse = True) #숫자 내림차순으로 정렬
sum_n = 0

if '0' not in n:	# 1번 조건 : 0이 없을 경우
    print(-1)
else:
    for i in n:
        sum_n += int(i) # 각 자리 수의 합 구하기
    if sum_n % 3 != 0:	# 2번 조건 : 3으로 나누어 떨어지지 않는 경우
        print(-1)
    else:	#모든 조건에 충족한다면 출력
        print(''.join(n))

 

 

 

다음과 같은 공식(?)이 있었다.

혹시 모르니.. 기억해놔야겠다!