[Python] BOJ(백준) 1744번 - 수 묶기

링크

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

난이도(solved.ac 참고)

골드4

추가로 시도해보면 좋은 반례 입력

6
1
1
1
1
1
1

추가로 시도해보면 좋은 반례 출력

6

풀이

 

이 문제를 풀 때 내가 기본적으로 생각했던 것

1. 양수는 1개 남을때까지 전부 2개씩 묶어서 곱해주고, 마지막 하나는 더해준다.

2. 음수는 역으로 sort한 뒤 전체 음수가 홀수개라면 1개 남을때까지 전부 2개씩 묶어서 곱해주고, 마지막 하나는 더해준다.

2-1. 짝수개라면 전부 묶어서 곱해준다.

3. 그리고, 매 if문이 끝날 때마다 두 원소를 모두 pop해줬고, 그에 맞춰 감소하는 빈도도 -2로 맞췄다. 왜냐면 매 반복문을 돌때마다 값이 두개씩 사라지니까.

4. 0은? 일단 고려 안했음

 -> 이 부분때문에 틀렸음. 왜냐면, 0은 음수 리스트에 넣어서 마지막 하나 남은 원소에 곱해줌으로써 마이너스 되는 값을 최소화 해줬어야 했기 때문

 

이 문제를 풀 때 추가적으로 고려해야 할 점

1. 양수의 경우에는 묶으려는 원소 두개 중 1이 있다면, 그 두개는 묶지 않고 각자 더해주는 게 더 크다. (2 * 1 < 2 + 1)

2. 0을 음수 리스트에 넣었고, 마지막 원소 두개 중 0이 포함되어 있다면 묶어서 - 값을 최소화시켜주는 게 더 크다.

 

그리고, 나는 pop을 했지만, 굳이 pop을 하지 않고도 충분히 풀 수 있는 것 같다. 코드를 줄여보려면 더 줄일 수 있겠으나, 귀찮으니까.. 어쨌든 해결

ㅋㅋ