1744 - 수 묶기

LeeKyoungChang·2022년 3월 26일

baekjoon greedy plzrun

Algorithm

목록 보기

74/203

📚 1744 - 수 묶기

수 묶기

이해

나 같은 경우, 모든 경우의 수를 조건식으로 처리했으나 이는 좋지 않은 방법이라는 것을 알게 되었다.

✔️ 좋은 해결책으로
음수는 오름차순 정렬, 양수는 내림차순 정렬, 1은 곱하기 대신 더하는 방식
(0은 음수에 속하게 된다.)

0과 음수의 개수 합이 홀수라면 제일 작은 값을 정답에 더한다.
0과 음수의 개수 합이 짝수라면 두 수를 곱하고 정답에 더한다.

소스

첫 나의 소스

import sys

read = sys.stdin.readline

n = int(read())

arr = []

minus_cnt = 0

for _ in range(n):
    d = int(read())
    arr.append(d)

    if d < 0: minus_cnt += 1

arr.sort()

result = 0
before = 0
cnt = 1
zero_check = False

check = False

for i in range(n - 1, -1, -1):
    # print("i : ", i, " arr : ", arr[i])
    # 양수일 때
    if arr[i] > 0:
        # 1에 도착할 시
        if arr[i] == 1:
            result += 1
            before = 0
        # cnt가 홀 수일 때
        elif cnt % 2:
            before = arr[i]
            result += before
        else:
            result += (before * arr[i])
            result -= before
            before = 0

        cnt += 1

    # 0일 때
    elif arr[i] == 0:
        # 음수자리가 홀 수이면 0이 존재한다면 곱해줘야 한다.
        if minus_cnt % 2 != 0:
            zero_check = True
    else:
        if not check:
            check = True
            cnt = 0
            # 만약 남은 음수들이 홀 수개라면
            if minus_cnt % 2 != 0:
                # 0이 존재한다면
                if zero_check:
                    result += 0 * arr[i]
                else:
                    result += arr[i]
            else:
                # 남은게 짝수라면
                cnt = 1
                before = arr[i]
        else:
            if cnt % 2:
                before = arr[i]
            else:
                result += (before * arr[i])
                before = 0
        cnt += 1

print(result)

좋은 해결책 소스

import sys

read = sys.stdin.readline

n = int(read())

arr = []

# 음수, 양수, 1 리스트 만들기
minus_list = []
plus_list = []
one_list = []
ans = 0

# 입력 값 받기
for i in range(n):
    input_num = int(input())
    if input_num > 1:
        plus_list.append(input_num)
    elif input_num  <= 0:
        minus_list.append(input_num)
    else:
        one_list.append(input_num)

plus_list.sort(reverse=True)
minus_list.sort()

# 양수 계산
# 양수의 개수가 홀수라면 제일 작은 값을 정답에 더하기
if len(plus_list) % 2 == 1:
    ans += plus_list[len(plus_list)-1]
    for j in range(0, len(plus_list)-1,2):
        ans += plus_list[j] * plus_list[j+1]
# 양수의 개수가 짝수면 두 수를 곱하고 정답에 더하기
else:
    for j in range(0, len(plus_list), 2):
        ans += plus_list[j] * plus_list[j+1]

# 음수 계산(0 포함)
# 음수의 개수가 홀수라면 제일 작은 값을 정답에 더하기
if len(minus_list) % 2 == 1:
    ans += minus_list[len(minus_list)-1]
    for j in range(0, len(minus_list)-1, 2):
        ans += (minus_list[j]) * (minus_list[j+1])
# 음수의 개수가 짝수면 두 수를 곱하고 정답에 더하기
else:
    for j in range(0, len(minus_list), 2):
        ans += (minus_list[j]) * (minus_list[j + 1])

# 수 1에 대한 계산
for j in range(len(one_list)):
    ans += one_list[j]

# 정답 출력
print(ans)