caffeinism7   1년 전

다이나믹 테이블을 다음과 같이 작성했습니다.


d[i][0] = i번째 칸이 텅 비어있고, 그전칸은 전부 다 찼을때

d[i][1] = i번쨰칸 윗쪽은 차있고, 그 전칸은 전부 다 찼을때

d[i][2] = i번째칸 아랫쪽은 차있고, 그 전칸은 전부 다 찼을때

d[i][3] = i번째칸 위아래 모두 차있고, 그 전칸도 모두 다 차있을때


그리하여 아래와 같은 소스로 그것을 구현했습니다. 하지만 이 문제는 원형으로 구현되어있어, N칸을 더 구현해 2n번째칸에서 n번째칸의 답을 빼서 제출했습니다.


하지만 칸수가 홀수일 때 문제가 발생했습니다. 왼쪽과 오른쪽이 맞닿아있는 원형에서는 두배로 만들었을때 실제와 만들 수 있는 값이 다르기 때문에 정답과 1이 차이나게 정답이 나지 않게 됩니다.


원형일때 이 다이나믹 테이블을 사용하여 이 현상을 고칠 수 있는 방법은 없을까요?

예외처리도 어렵고.. 그렇네요

저같은 경우엔 그냥 아래의 경우를 따로따로 다 구해서(배열을 초기화하고 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를 출력하도록 고치는 데까지 했습니다.

yukariko   1년 전

저는 원형 dp같은 문제를 만나면 선형으로 분리시켜서 답을 구했습니다.

이 문제는 N-1 열과 0 열이 서로 묶일 때 원형이 되는데,

처음부터 N-1 과 0열을 묶은 상태에서 1 ~ N-2 까지의 답을 구한것과

0 ~ N-1의 선형의 답을 구한것을 따로구해 최소값을 구해줬습니다.

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