[백준] 1744번 : 수 묶기 (Python / 파이썬)

문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

 

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

 

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

조건 및 입출력

- 첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

- 수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 2^31보다 작다.

- 시간 제한: 2초 / 메모리 제한: 128MB

 

코드 (Python 3)

trys=int(input());

result=0;
minus=[]; plus=[];

#구현 방향 -> 음수는 서로 곱해서 양수를 만들거나, 0과 곱한 뒤 더하는 방향으로 처리.
for i in range(trys):
    temp_num=int(input());
    if(temp_num<=0): #음수(0포함)
        minus.append(temp_num);
    elif(temp_num==1):
        result+=1; # 1은 어떤 수를 곱해도 1이므로, 무조건 더해야 함.
    else: #양수
        plus.append(temp_num);

minus.sort(); plus.sort();

#음수 처리
while(len(minus)>1): #하나씩 빼자->pop 연산자 특징
    result+=minus.pop(0)*minus.pop(0);  #2개씩 빼므로, while 조건 1보다 큰 경우로 설정
if(len(minus)==1):
    result+=minus.pop(); #홀수 개 처리 규칙

#양수 처리
while(len(plus)>1):
    result+=plus.pop()*plus.pop();
if(len(plus)==1):
    result+=plus.pop();

print(result);

 

 

---

여담

처음에는 막 복잡하게 스파게티 코드로 제출했다. 물론 오답처리 되었다.

학기 중에 C를 많이해서 그런지, 사고 방식이 C로 굳어진 느낌이다.

 

그러다보니, 파이썬의 강력한 메소드를 잊고 있었다.

때 마침 pop 함수가 기억이 났다. pop 함수를 쓰니 금방 문제를 풀 수 있었으며 기존 코드 대비 1/3로 줄었다...ㅋㅋ;

 

처음에 어떻게 구현할 것인지 방향을 정해놓고 하는 것이 좋을 듯하다.

이번 학기 교수님께서 '코딩은 구현하고자 하는 방향(원칙)만 정해도 절반 이상을 한 것이다.'라는 말씀을 하셨는데, 그 말씀에 공감이 된다.

 

처음에 수를 입력받으면, 어떻게 이 수를 처리할 것인지만 생각했다면,

그 뒤는 프로그래밍 실력에 의존하는 듯 하다.

 

1. 음수는 작은 음수 두개 곱해서 양수로 만들거나, 그렇지 않을 경우 0이랑 곱해서 음수를 최대한 없앤다는 원칙.

2. 1은 어떤 수와 곱해도 1이므로 무조건 더해야 한다는 원칙.

3. 양수는 큰수끼리 곱해서 더해야 한다는 원칙,

 

이 세 가지만 떠올렸다면, 크게 어렵지 않게 풀 수 있을 것이다.

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면, 알려주세요 :)