본문 바로가기

카테고리 없음

[백준 1422번] 숫자의 신 (Python3)

K,N = map(int,input().split())

nums = []
for _ in range(K):
  n = input()
  x = n*(18//len(n))
  for i in range(18%len(n)):
    x += n[i]
  nums.append((len(n),x,n))
nums.sort(reverse=True)

for _ in range(N-K):
  nums.append(nums[0])
nums1 = []
for i in range(N):
  l,x,n = nums[i]
  nums1.append((x,n))
nums1.sort(reverse=True)

for i in range(N):
  print(nums1[i][1],end="")

큰 수 만들기 [백준 16496번] 큰 수 만들기 (Python3) (tistory.com) 의 약간 업그레이드 문제

기본적인 알고리즘은 큰 수 만들기와 똑같다. 다만 큰 수 만들기는 모든 숫자를 1개씩만 사용하는 반면 이 문제는 중복해서 사용하는 경우가 존재한다.

하지만 어려울 것이 없는게, 어차피 가장 큰 수를 만들어 주는 숫자 1개만 중복해서 사용하고 나머지 숫자는 1번씩 사용하는게 최선이기 때문에 가장 큰 수를 만들어줄 숫자 1개를 찾아주면 된다.

 

정렬방식은 큰 수 만들기와 똑같은데, 중복해서 사용하는 숫자를 뽑을때는 "길이"에 주의해야 한다. 9가 10보다 큰 수 만들기는 유리하지만 중복해서 뽑는 경우에는 10을 여러번 사용해야하기 때문이다.

 

따라서 길이를 최우선으로 정렬하여 그 중에서 가장 큰 수를 N-K번 추가한 후, 큰 수 만들기 문제와 똑같이 풀면 된다.

 

 

오늘의 교훈) 다양한 문제를 해결하자