그리디 알고리즘 연습 - 곱해서 최대가 되도록, 더해서 최소가 되도록 나누기

1. 문제

 

20915번: 숫자 카드 놀이 (acmicpc.net)

20915번: 숫자 카드 놀이

 

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. 문제

 

9440번: 숫자 더하기 (acmicpc.net)

9440번: 숫자 더하기

 

 

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)