반례입니다

감사합니당ㅜㅜ

<오답노트>

1. 내 방법 : dp 배열을 쓰지 않고 처음 n=2일때부터 시작해 / 대각선에서 시작하는 경우 \ 대각선에서 시작하는 경우 2가지로 나눠서 sum, sum2를 구하고 둘의 크기를 비교해서 단순히 답을 구했다. 

2. 내 방법 문제점: 2xn 을 구할 때, 2x(n-1) 만 고려해서 2xn의 답을 구했다. 그래서 시작점을 2가지로 나눠서 구하고 코드에 여러가지 조건을 추가하는 등 나름 노력을 했지만 반례를 다 잡지 못했다.

3. 구글링 한 방법 : 2xn 짜리 dp 배열을  만들었고, dp[i][j] 값 = 가로줄이 n일 경우 i번째줄 스티커를 고르면서 끝났을 때의 최고값 이다. 그 중에서 i번째줄 스티커를 마지막으로 땠을 때, 2번째 뒤 n-1에서 한 줄 띄고 마지막 스티커를 고를경우 아니면 지그재그로 고를 경우로 나눠서 둘중에 큰 값을 고르고 n을 1늘릴때마다 스티커 2개가 추가되니까 또 그 2가지 경우의 최대값을 골라서 dp배열에 저장한다. 

저 방법으로 고칠거긴한데 왜 구글링해서 나오는 방법은 다 똑같이 저 방법을 썼을까요?  서로 어디서 배껴온 방법이 아니라면 저빼고 다들 똑같이 좋은 방법을 생각하는것같아요ㅜㅜ

@lambda

첫째, 셋째 열에서 30을 고르고 다섯째, 여섯째 행에서 19, 14 고르면 해답 93 아닌가요?

@lsh0426 그렇긴한데 그냥 덧셈을 잘못하신거같아요! 제가 틀렸다는걸 알려주시려고..

이 게시물의 댓글을 통해 예시를 들어주신
해당 반례의 정답은 93이 맞습니다.

댓글을 읽는 분들께서는 혼동하지 않으시길 바랍니다.

@lambda 읽어주시고 고쳐주시면 정말 감사하겠습니다.

입력:

1
6
20 5 30 9 19 0
30 9 10 0 30 14

정답출력:

93