10257번 - 얼룩
런타임 에러도 납니다. 이 경우는 배열 인덱스를 잘못 참조해서 나타나는 예이겠지요?
문제가 되는 데이터 입니다. 컴파일러는 쓸 수 없어서 ideone에서 확인한 것입니다.
두 분의 답변 감사합니다. 곰곰이 생각해보니 아래 그림과 같은 경우가 문제될 수 있겠네요.
idx열 처리할 때 빨간색 청소도구를 두면 idx열에는 얼룩이 존재하지 않게 됩니다. 그래서 isPossible이 true를 반환해줍니다.
이어서 Find 함수가 다음 상태를 결정짓기 위해 States 배열을 순회할 것입니다. 그런데 idx-1 열의 초록색으로 표시된 얼룩이 빨간색 청소도구로 인해 1로 바뀌게됩니다. 그런데 States 배열에는 연속된 4개 비트가 1인 경우는 존재하지 않으므로 29를 반환하게 됩니다. (0 ~ 28 까지가 유효한 리턴값인데...)
그래서 wrong answer, runtime error 등이 나타나게 되는 것 같습니다.
이 문제를 해결하기 위해 각 열의 상태를 "정확하게" 나타내기 위해 dp 배열을 다음과 같이 선언해야 되나 생각했습니다.
dp[1000+1][(1<<10)][(1<<10)]
그런데 이렇게 선언해버리면 분명 메모리 초과입니다.
29가지 상태로 나타내야 하는것이 맞는 것 같은데 위의 그림처럼 인접한 네개 비트가 1인 경우에 대해서는 어떻게 처리할 수 있는지 궁금합니다.
댓글을 작성하려면 로그인해야 합니다.
juhyun16 5년 전
처음에 어떻게 접근해야할지 몰라서 해설을 찾아봤습니다. 해설대로 구현해보려 하는데 제가 잘못한 부분이 있는 것 같습니다. 채점을 해보니 틀렸습니다가 나오네요. 생각해봤지만 어느부분이 틀렸는지 잘 모르겠어서 질문남깁니다.
제가 구현하고자 했던 방식은 아래와 같습니다.
먼저, 동적계획법을 푸는 재귀함수를 만들고자 했습니다.
int dfs(int idx, int current, int previous)
로 설계했고 3차원 DP를 푸는 함수입니다.
// 1번째 열 ~ idx번째 열까지의 매트릭스에 대해 모든 얼룩을 제거하기 위해 필요한 청소도구의 최소 갯수를 반환한다.
// current : 현재 열의 청소상태(단, 얼룩의 상태를 보기 위해선 map 배열을 참조해야함).
// previous : 이전 열(idx-1)의 청소상태(단, 얼룩의 상태를 보기 위해선 map 배열을 참조해야함).
dfs 함수 내에서 idx번째 열을 처리할 때 3 by 3 청소도구를 두게 되는데 이 때 뒤쪽 열(idx+1, idx+2)에는 영향을 끼치지 않고 현재 열(idx) 포함 오직 이전 열(idx-1, idx-2)에만 영향을 끼칠 수 있다고 생각했습니다.
그래서 아래 그림과 같이 idx 열에 대해 작업 중 일땐 오직 빨간색, 파란색과 같은 형태로만 얼룩들을 지울 수 있다고 생각했습니다.
재귀 함수내에서 다음 함수를 호출할 때는 dfs(idx-1, , ) 형태로 이루어지게 되고 그러면 idx 열에는 얼룩이 없음이 보장되어야 한다고 생각했습니다. 그래서 이를 확인하는 작업이 dfs() 함수 내에서 isPossible()을 호출함으로써 검사하게 됩니다.
isPossible 함수가 true를 반환할 때만 dfs 함수는 idx-1에 대해 호출하도록 구현했습니다.
제가 해설의 어느 부분을 잘못이해하고 잘못 코딩한 것인지 한번 봐주시면 감사하겠습니다.
-------------------------------------------------------------------------------------------------------------------------
아래 그림은 제가 input을 어떻게 처리했는지 나타내는 그림입니다. 2차원 배열이 아닌 int 형의 1차원 배열을 선언했습니다. 1차원 배열 각각의 정수에서 특정 번째 비트가 2차원 배열에서의 행 역할을 하도록 했습니다. 그리고 얼룩은 비트 0으로 표현했습니다.
아래는 저의 코드 입니다. 긴글 읽어주셔서 감사합니다.