[Python/백준] 1744 수 묶기

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

1744번: 수 묶기

<문제 해설>

그리디 문제이다. 

1. 입력받은 숫자들을 오름차순으로 정렬해준다.
2. 양수 숫자들은 큰수부터 2개씩 곱해서 더해준다.
3.  1*1 보다 1+1이 더 큰 수라는 것에 유의한다.
4. 양수가 하나남으면 그냥 더해주면 된다.
5. 음수 숫자들은 작은수부터 2개씩 곱해서 더해준다.
6. 음수가 하나남고 0도 남았을 경우 서로 곱해서 더해준다.
7. 0이 안남고 음수가 하나 남았으면 그냥 더해주면 된다.

<예시>

위 사진의 계산식은 문제 해설에 적은 방법들을 예제에 적용해서 적은 모습이다.

2번 예제를 보면 뒤에서 부터(큰수 부터) 2개씩 묶어서 최대값이 나오는 걸 볼 수 있다.

5번 예제를 보면 앞에서 부터(가장 작은 수부터) 2개씩 묶어서 최대값이 나오는 걸 볼 수 있다.

4번 예제를 보면 음수에 0을 곱해서 최대값을 만들어준다.

6번 예제를 보면 1*1을 해주는 것이 아니라 1+1을해서 최대값이 나오는 걸 볼 수 있다.

<코드>

N = int(input())

numbers = []

for i in range(N):
    numbers.append(int(input()))

numbers.sort()

output = 0

while(1):
    a = numbers.pop()
    if len(numbers) == 0:
        output += a
        break
    if a <= 0:
        numbers.append(a)
        break
    else:
        b = numbers.pop()
        if b <= 0:
            output += a
            numbers.append(b)
            break
        output += max(a*b,a+b)
        if len(numbers) == 0:
            break
        
i = 0
lenth = len(numbers)
if lenth > 0:
    while(1):
        a = numbers[i]
        if i+1 >= lenth:
            output += a
            break
        else:
            i += 1
            b = numbers[i]
            output += (a*b)
            if i+1 >= lenth:
                break
            else:
                i += 1

print(output)

<코드 설명>

N = int(input()) //N값 정수로 받아오기

numbers = [] //숫자들을 저장할 배열 

for i in range(N): //N만큼 반복하면서 배열에 숫자 정수로 저장
    numbers.append(int(input()))

numbers.sort() //받은 숫자들을 정렬

output = 0 //출력해줄 답을 0으로 초기화

while(1): //계속 반복
    a = numbers.pop() //숫자를 뒤에서 하나 빼서 a에 저장(남아있는 양수중 가장 큰수 꺼내기)
    if len(numbers) == 0: //숫자를 모두 빼냈으면 숫자가 하나 남은거니 무조건 더해줘야함
        output += a //출력값에 더해주고
        break //반복문 정지
    if a <= 0: //만약 a가 0이거나 음수라면
        numbers.append(a) //0과 음수 계산은 아래있는 반복문에서 진행하니 꺼낸 값 다시 넣어주고
        break //정지
    else: //a가 양수라면
        b = numbers.pop() //남아있는 양수중 가장 큰수 빼서 b에 저장
        if b <= 0: //b가 음수거나 0이라면 아래있는 반복문에서 진행하니
            output += a //a값만 출력값에 더해주고
            numbers.append(b) //다시 쓸 수니 배열에 넣어주기
            break //반복문 정지
        output += max(a*b,a+b) // 1+1이 1*1보다 큰걸 알아야하니 비교해서 출력값에 넣어주기
        if len(numbers) == 0: //b를 빼냈을 때 배열이 었으면
            break //정지
        
i = 0 //이번엔 앞에서부터 계산할 것이니 인덱스 i를 가장 앞(음수중 가장 작은 값)으로 설정
lenth = len(numbers) //숫자 리스트 길이 계속 계산할 필요 없게 lenth에 저장
if lenth > 0: //남은 숫자가 없으면 계산할 필요도 없으니 조건문 걸기
    while(1): //계속 반복
        a = numbers[i] //a에 숫자 저장
        if i+1 >= lenth: //a만 남았을 경우
            output += a //무조건 출력에 더해줘야 하니 더하기
            break //모든 수를 다 계산한 것이니 정지
        else: //2개 이상 남았을 경우
            i += 1 //인덱스 증가
            b = numbers[i] //b에 증가한 인덱스에 있는 값 저장
            output += (a*b) //2수를 곱해서 더한다.
            if i+1 >= lenth: //인덱스가 리스트 길이보다 크면 에러가 생길테니 
                break //정지
            else: //인덱스가 길이보다 작으면
                i += 1 //인덱스 증가

print(output) //답 출력해주기