저같은 경우엔 그냥 아래의 경우를 따로따로 다 구해서(배열을 초기화하고 dp를 따로 다 돌려서) 아래 중 가장 큰 값을 출력했습니다.
이프문으로 하드코딩..
1) 1번 열과 n번 열 사이에 묶임이 없을 때
2) n번 열의 첫줄-1번 열의 첫줄이 묶일 때 (묶일 수 있으며, 반드시 묶일 때)
3) n번 열의 둘째 줄-1번 열의 둘째 줄이 묶일 때
4) n번 열의 첫줄-1번 열의 첫줄, n번 열의 둘째 줄-1번 열의 둘째 줄이 각각 묶일 때
5) n번 열의 첫째 줄과 둘째 줄이 묶일 때, 1번 열의 첫째 줄과 둘째 줄이 묶일 때, 둘다 묶일 때
예외로는 각 케이스마다 불가능한 경우, 예를 들어 2)번의 케이스 같은 경우엔 n번 열의 첫줄-둘째 줄이 묶이거나, 1번 열의 첫줄과 2번 열의 첫줄이 묶이는 등의 경우는
불가능한 것으로 판정하도록 하였습니다.
근데 이렇게 하면 n=1일 때 오답 나오더라구요. n=1일 때는 또 이프문으로 케이스 분류해서 1 혹은 2를 출력하도록 고치는 데까지 했습니다.
caffeinism7 9년 전
다이나믹 테이블을 다음과 같이 작성했습니다.
d[i][0] = i번째 칸이 텅 비어있고, 그전칸은 전부 다 찼을때
d[i][1] = i번쨰칸 윗쪽은 차있고, 그 전칸은 전부 다 찼을때
d[i][2] = i번째칸 아랫쪽은 차있고, 그 전칸은 전부 다 찼을때
d[i][3] = i번째칸 위아래 모두 차있고, 그 전칸도 모두 다 차있을때
그리하여 아래와 같은 소스로 그것을 구현했습니다. 하지만 이 문제는 원형으로 구현되어있어, N칸을 더 구현해 2n번째칸에서 n번째칸의 답을 빼서 제출했습니다.
하지만 칸수가 홀수일 때 문제가 발생했습니다. 왼쪽과 오른쪽이 맞닿아있는 원형에서는 두배로 만들었을때 실제와 만들 수 있는 값이 다르기 때문에 정답과 1이 차이나게 정답이 나지 않게 됩니다.
원형일때 이 다이나믹 테이블을 사용하여 이 현상을 고칠 수 있는 방법은 없을까요?
예외처리도 어렵고.. 그렇네요