그리디 알고리즘 연습 - 곱해서 최대가 되도록, 더해서 최소가 되도록 나누기
1. 문제
20915번: 숫자 카드 놀이 (acmicpc.net)
2. 풀이
숫자를 두 부분으로 나눠서 곱했을때, 최대가 되도록 만들기
두 부분은 적어도 하나의 숫자를 반드시 포함해야한다
6이나 9는 회전해도 구분할 수 없으니 회전해서 사용가능하다.
그렇다면 곱했을때 최대가 될려면 6은 무조건 9로 만들어서 사용하는게 유리하다.
또한 두 수의 곱이 최대가 될려면, 앞자리에는 무조건 큰 수가 오는게 유리하다
또한 두 수 a,b에 대하여 그 차이를 a - b = x라고 하자.
두 수의 곱 a*b = a * (a-x)이므로, x가 작을수록 a*b가 커진다.
따라서, 두 수의 차이가 작을수록 두 수의 곱이 커진다.
그러므로 먼저 6은 9로 바꿔주고,
숫자카드를 내림차순으로 정렬한 다음, 최소한 하나씩은 사용해야하므로 두 부분에 각각 하나씩은 분배해놓는다
그리고 숫자카드를 순회해서, 두 숫자를 비교한 다음 첫번째 수가 더 크다면, 두번째 수에 숫자를 붙여주고
두번째 수가 더 크다면 첫번째 수에 숫자를 붙여서 두 수의 차이를 매번 줄여준다
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
s = list(stdin.readline().rstrip())
#6은 9로 바꿔준다
for i in range(len(s)):
if s[i] == '6':
s[i] = '9'
#큰 수부터 사용하도록 내림차순 정렬
s.sort(reverse = True)
#최소한 하나의 수는 사용해야하므로, 각 수에 하나씩 분배
n1 = [s[0]]
n2 = [s[1]]
#두 수의 차이가 작을수록 두 수의 곱이 커지므로,
#매번 두 수를 비교해서 첫번째 수가 더 크다면, 두번째 수에 숫자를 붙여주고
#두번째 수가 더 크다면, 첫번째 수에 숫자를 붙여줘서 두 수의 차이를 매번 줄여준다
for i in range(2,len(s)):
k1 = int(''.join(n1))
k2 = int(''.join(n2))
if k1 < k2:
n1.append(s[i])
else:
n2.append(s[i])
n1 = int(''.join(n1))
n2 = int(''.join(n2))
print(n1*n2)
3. 문제
4. 풀이
이번엔 두 부분으로 나눴을때, 합이 최소가 되도록 나누는 것이다
합이 최소가 될려면 최대한 동일한 개수의 숫자카드로 나눠줘야한다.
조금만 생각해봐도, 8개의 숫자카드가 있는데 2자리 + 6자리 = 6자리 수, 3자리 + 5자리 = 5자리 수, 4자리 + 4자리 = 4자리 수가 되니까...
또한 합이 최소가 될려면 앞자리에는 무조건 작은 수가 와야할 것이다.
따라서, 숫자카드를 정렬하고, 작은 수부터 첫번째 부분과 두번째 부분에 차례대로 배분해준다
작은 수부터 주기 시작하면 문제는 맨 앞자리에 0이 오는 경우가 생긴다는 것이다
예를 들어 [0,1,2,3,4,0,1,2,3]은, 정렬하면 [0,0,1,1,2,2,3,3,4]인데 9개니까 먼저 1개를 한쪽에 준다
[0]
[]
그리고 [0,1,1,2,2,3,3,4]를 다시 한쪽 부터 차례대로 배분해주면...
[1,1,2,2,3,3,4]
[0,0]
[]
[1,2,2,3,3,4]
[0,0]
[1]
[2,2,3,3,4]
[0,0,1]
[1]
[2,3,3,4]
[0,0,1]
[1,2]
[3,3,4]
[0,0,1,2]
[1,2]
[3,4]
[0,0,1,2]
[1,2,3]
[4]
[0,0,1,2,3]
[1,2,3]
[0,0,1,2,3]
[1,2,3,4]
이 상태에서 두번째 수야 1234로 될것이지만... 첫번째 수는 그냥 하면 123이 되어서 0,0이 지워지니까 오답
최소로 만들려면? 처음으로 0이 아닌 수의 위치를 맨 앞으로 옮겨주면 된다
[0,0,1,2,3] >>> [1,0,0,2,3]
따라서, 10023 + 1234 = 11257이 최솟값이 된다.
from sys import stdin
while 1:
A = stdin.readline().rstrip().split()
if len(A) == 1:
break
else:
n = int(A[0])
a = A[1:]
#숫자카드를 정렬하고,
a.sort(reverse = True)
n2 = n//2
n1 = n - n2
a1 = []
a2 = []
#숫자 카드 개수가 홀수개이면, 한개를 한쪽에 주고
if n % 2 == 1:
a1.append(a.pop())
one = True
#작은 수부터 차례대로 양쪽에 배분해준다
while a:
if one:
a1.append(a.pop())
one = False
else:
a2.append(a.pop())
one = True
#0이 있는 경우에 대한 예외 처리
#a1,a2가 작은 수부터 정렬된 상태
#처음으로 0이 아닌 수를 찾았다면, 맨 앞으로 옮겨주면 된다
for i in range(len(a1)):
if a1[i] != '0':
a1[0],a1[i] = a1[i],a1[0]
break
for i in range(len(a2)):
if a2[i] != '0':
a2[0],a2[i] = a2[i],a2[0]
break
a1 = int(''.join(a1))
a2 = int(''.join(a2))
print(a1+a2)
'알고리즘 > 그리디 알고리즘' 카테고리의 다른 글
코딩테스트 복기 - 당장 행동하지 않고 나중에 필요할 때 행동하는 그리디 알고리즘 테크닉 (0) | 2024.02.10 |
---|---|
경이로운 그리디 알고리즘 5 -인접한 원소간 차이의 최댓값을 최소로 만드는 방법- (0) | 2023.11.07 |
두 종류 물건을 특정 개수만큼 사면서 최소 가격에 사는 그리디 알고리즘 (0) | 2023.09.25 |
그리디 기초 테크닉 익히기2 - 특별한 정렬, 사고 전환, 상쇄, 올바른 순서 부분문자열 몇개 있는지, 원소 상태 바꾸기- (0) | 2023.09.13 |
제켄도르프 분해 응용 - 정수를 피보나치 수의 합과 차로 표현하기 (0) | 2023.09.13 |