숫자박스 > 문제은행

본문 바로가기


알고리즘 다이나믹2

1083 : 숫자박스

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 27 회    시도횟수: 296 회   



그림과 같이 숫자 박스는 위와 아래의 두 행과 N개의 열로 나누어져 있다. 따라서 숫자 박스는 전체 2N개의 칸으로 이루어져 있고, 각 칸에는 0 이 아닌 -10 이상 10 이하의 정수가 적힌 숫자판이 들어 갈 수 있다.
아래 그림은 N=7 인 경우 어떤 숫자 박스의 상태를 보여주고 있다. 빈칸은 숫자판이 들어있지 않은 칸을 나타내며, 위와 아래의 행에 들어있는 숫자판의 개수는 같지 않을 수도 있다.

 

e3050b66a1b29a01767400d7560a4131_1449735

 

숫자 박스의 "값"은 각 열의 위와 아래에 있는 두 숫자들의 곱을 모두 더한 값으로 정의된다. 빈칸은 0으로 계산한다. 예를 들면, 위 그림의 숫자 박스의 값은 (-3)x0+(-1)x(-3)+(-2)x2+0x4+5x0+(-1)x5+0x(-2)=-6이다.

 

각 행에 주어진 숫자판들에 대해 그 순서를 유지하면서 좌우로 움직이면 다른 숫자 박스의 "값"을 얻을 수 있다. 위의 예에서 윗 행에 있는 5와 -1을 오른쪽으로 각각 한 칸씩 옮기고, 아래 행의 -3을 왼쪽으로 한 칸, 2와 4를 오른쪽으로 각각 한 칸씩 옮기면 그 결과 숫자 박스는 다음과 같다.

 

e3050b66a1b29a01767400d7560a4131_1449735

 

이 숫자 박스의 "값"은 9+25+2=36이 된다. 주어진 숫자 박스의 위와 아래의 행에 놓인 숫자판들을 그 순서는 유지하면서 위의 조건을 만족하도록 움직여서 얻을 수 있는 숫자 박스의 최대값을 구하는 프로그램을 작성하시오.

 

숫자판들은 좌우 빈칸으로만 움직일 수 있으며, 건너뛰는 형태로 다른 숫자판과 그 위치가 교환될 수는 없다. 다시 말하면, 빈칸을 제외하면 각 행의 숫자판들의 순서는 항상 그대로 유지되어야 한다. 부분 점수는 없다.


첫 줄에는 숫자 박스의 열의 수를 나타내는 정수 N(1≤N≤400)이 주어진다. 그 다음 두 줄에는 각각 숫자 박스의 위와 아래의 행에 놓인 초기 숫자판들의 숫자가 하나 이상의 공백을 두고 나타나는데, 숫자판이 없는 빈칸은 0으로 표시된다. 
단, 숫자판의 숫자는 모두 -10 이상 10 이하의 0이 아닌 정수이다.


입력으로 주어진 숫자 박스의 각 행의 숫자판들을 가로로 이동시켜 얻을 수 있는 숫자 박스의 최대값을 첫 번째 줄에 출력한다.

[Copy]
7
-3 -1 -2 0 5 -1 0
0 -3 2 4 0 5 -2
[Copy]
36






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.