tldnjs0821   1년 전

조금 다른 방식으로 풀어봤습니다.

최대가 4x4이기 때문에 주어진 배열을 4x4배열의 오른쪽 아래에 옮깁니다.

예를 들어

123
312

가 주어지면

0000
0000
0123
0312

위처럼 배열에 저장합니다.

그리고 각 행마다 인덱스0부터 4까지의 열에 1000, 100, 10, 1 을 곱하고 그 값을 모두 더한 것이 결국 최대아닐까요?

각 행의 인덱스0에 들어있는 수가 0이든 아니든 각 행의 인덱스0을 세로로 더해봤자 각 행의 가로를 모두 더한 값보다 작을 것이라고 생각합니다.

각 열에 대해서도 위처럼 1000, 100, 10, 1을 곱해 더한 값을 구해서 열과 행에 대해 더한 값 중 더 큰 값을 출력하면 최댓값일 것 같습니다.

글로 설명하려니 조금 힘드네요.

혹시 반례가 있을까요?

adfsfsf   1년 전

반례입니다. 이 경우는 2000만 떼어낸 후, 방향을 바꿔서 10+21로 하는 것이 12+1보다 큽니다.

adfsfsf   1년 전

보니까 이게 가장 적합한 거 같네요.

1. 4개의 테두리 중에서 가장 큰 수가 되는 테두리를 잘라낸다.

2. 남은 종이가 가로 혹은 세로로 한 줄이 될 때까지 1번을 반복한다.

3. 잘라낸 종이들의 합을 더한다.

tldnjs0821   1년 전

반례 감사합니다.

알려주신 걸 잘 적용해서 다시 풀어봐야겠네요.

댓글을 작성하려면 로그인해야 합니다.