[백준 1744번] 수 묶기 - 파이썬

 

문제 링크:

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

1744번: 수 묶기

 

---

풀이 과정:

첫 번째 접근 방법

수를 오름차순 정렬한 후에 두 수를 곱하고 이를 정답 값에 대입하면 최적의 해가 도출될까??

코드를 작성해보았더니 예제의 정답값과 모두 맞았지만 반례가 존재했다.

n = 5이고 다음과 같은 5개의 숫자를 입력했을 때 (-537, -435), (81, 157), (257) 이렇게 묶어서 답이 출력된다.

(81, 157)이 아니라 (157 * 257)로 묶여야 최댓값을 도출할 수 있다.

5
-537
81
-435
257
157

 

두번째 접근 방법

음수, 양수, 그리고 1을 케이스별로 리스트를 나누어 계산해보면 어떨까??

음수는 오름차순 정렬, 양수는 내림차순 정렬, 1은 곱하기 대신 더하는 방식으로 말이다.

(여기서 0은 음수에 속하게 된다. 수 묶음이 (음수, 0)이 되어야 손해를 적게 본다.)

이렇게 한다면 최적의 해를 도출할 수 있을 것이다. 이제 코드를 작성해보자.

 

풀이 코드:

# 1744번 수 묶기

n = int(input())

# 음수, 양수, 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)

 

문제를 풀면서 느낀 점은 항상 내가 생각한 방식의 반례가 있는지 찾아보는 것이 중요하다. 

나는 백준의 질문검색을 통해 반례 예시를 대입하여 내 풀이와 일치한 지 확인해본다.

소스코드 작성이 끝나면 이 질문검색을 통해 게시판에 올려진 코드들을 분석해보면서 복습할 수 있다.

https://www.acmicpc.net/board/search/all/problem/1744

게시판 검색 - 1 페이지

 

 

1744번 수 묶기