포도주(wineSeq)를 입력 받으면서 값이 0인 포도주 잔을 맨 앞에 1개, 맨 뒤에 2개 추가로 놓습니다 따라서 입력으로 주어진 포도주 잔은 1~n번 인덱스에 위치하게 됩니다
뒤에 추가로 2잔을 더 둔 이유는 BFS 과정에서 1칸 전진, 2칸 전진, 3칸 전진을 수행하기 때문입니다
BFS를 수행하는 동안 maxAmount라는 이름의 2 x (n + 1) 크기의 2차원 배열(이중 벡터)에 최대 누적 포도주 시음량(=최대 누적값)을 기록합니다
maxAmount의 2번째 인덱스는 wineSeq 상의 뒤에 추가로 놓은 포도주 2잔을 제외한 모든 포도주 잔과 1대1로 대응되며, 1번째 인덱스는 평소엔 0번만 사용되다가 포도주를 연속적으로 마신 경우(2잔 연달아 마신 경우)에 1번을 사용합니다
예를 들어, 입력으로 6, 6, 10, 13, 9, 8, 1이 주어졌을 때 제 코드는 1번째 잔, 2번째 잔, 3번째 잔, 1번째 잔에서 1칸 나아가서 2번째 잔 ... 순서로 탐색을 하게 됩니다
이 때 maxAmount는 [0][1] = 6, [0][2] = 10, [0][3] = 13, [1][2] = 16 ... 이 됩니다
또한, 3잔을 연달아 마시게 되는 경우는 코드의 19번 라인인 nextCnt == 2 조건에 의해 탐색하지 않습니다
마지막으로, BFS 과정에서 마지막 잔을 넘어가서 뒤에 추가로 둔 2개의 값이 0인 포도주 잔에 도달할 경우, maxAmount에 대입할 최대 누적값 계산을 먼저 한 뒤에 그 값을 maxAmount[0][n]에 저장합니다 이는 마지막 잔을 마시지 않는 경우도 빼먹지 않고 탐색하기 위함입니다 ([1][n]은 사용하지 않습니다 관련해서는 코드의 31~35번 라인 if문 확인해주세요)
60%대에서 오답 처리가 되던데 반례를 도무지 찾을 수가 없어서 질문 올려봅니다
DP로 정답 코드를 짜는 것과는 별개로 처음 스스로 생각한 로직의 어디에 구멍이 있는지가 알고 싶습니다
jhwon1009 1년 전
뒤늦게 DP로 푸는 문제라는 걸 깨달았습니다
우선 DFS로 접근했다가 TLE가 발생해서 BFS로 접근했습니다
포도주(wineSeq)를 입력 받으면서 값이 0인 포도주 잔을 맨 앞에 1개, 맨 뒤에 2개 추가로 놓습니다 따라서 입력으로 주어진 포도주 잔은 1~n번 인덱스에 위치하게 됩니다
뒤에 추가로 2잔을 더 둔 이유는 BFS 과정에서 1칸 전진, 2칸 전진, 3칸 전진을 수행하기 때문입니다
BFS를 수행하는 동안 maxAmount라는 이름의 2 x (n + 1) 크기의 2차원 배열(이중 벡터)에 최대 누적 포도주 시음량(=최대 누적값)을 기록합니다
maxAmount의 2번째 인덱스는 wineSeq 상의 뒤에 추가로 놓은 포도주 2잔을 제외한 모든 포도주 잔과 1대1로 대응되며, 1번째 인덱스는 평소엔 0번만 사용되다가 포도주를 연속적으로 마신 경우(2잔 연달아 마신 경우)에 1번을 사용합니다
예를 들어, 입력으로 6, 6, 10, 13, 9, 8, 1이 주어졌을 때 제 코드는 1번째 잔, 2번째 잔, 3번째 잔, 1번째 잔에서 1칸 나아가서 2번째 잔 ... 순서로 탐색을 하게 됩니다
이 때 maxAmount는 [0][1] = 6, [0][2] = 10, [0][3] = 13, [1][2] = 16 ... 이 됩니다
또한, 3잔을 연달아 마시게 되는 경우는 코드의 19번 라인인 nextCnt == 2 조건에 의해 탐색하지 않습니다
마지막으로, BFS 과정에서 마지막 잔을 넘어가서 뒤에 추가로 둔 2개의 값이 0인 포도주 잔에 도달할 경우, maxAmount에 대입할 최대 누적값 계산을 먼저 한 뒤에 그 값을 maxAmount[0][n]에 저장합니다 이는 마지막 잔을 마시지 않는 경우도 빼먹지 않고 탐색하기 위함입니다 ([1][n]은 사용하지 않습니다 관련해서는 코드의 31~35번 라인 if문 확인해주세요)
60%대에서 오답 처리가 되던데 반례를 도무지 찾을 수가 없어서 질문 올려봅니다
DP로 정답 코드를 짜는 것과는 별개로 처음 스스로 생각한 로직의 어디에 구멍이 있는지가 알고 싶습니다