2630번 - 색종이 만들기
분할정복을 이용하는건 알겠는데, 어떻게 구현해야될지 감이 안잡히네요.
문제를 보고
① '일단 2차원 배열을 선언 후, 내가 입력한 색종이 인풋을 저장해야겠다'
② 색종이를 4등분 분할 후, 각 종이마다 흰색이나 파란색으로 꽉차있는지 아닌지 검사하고
③ if(꽉차있을 시) --> 분할을 멈추고,
else --> ②를 반복한다.
이런 계획은 세워놓았는데, 구현한건 ①밖에 없네요.. 배열에 넣었는 놨는데 이거를
4등분하는 코드를 어떻게 작성해야할지도 모르겠네요. 사실 배열에 저장하는게 효율적인 방법일지도 의문이고요ㅠ
1시간정도 고민하다가 질문 올려봅니다. 이 문제를 어떻게 해결해나가야할까요?ㅠㅠ
재귀 호출을 이용하면 편리하게 구현할 수 있습니다.
(x,y)에서 길이가 l인 정사각형을 검사하는 것을 go(int x, int y, int l)와 같은식으로 구현을 했다면
4등분하는 코드는
go(x, y, l/2)
go(x,y+l/2,l/2)
go(x+l/2,y,l/2)
go(x+l/2,y+l/2,l/2)
로 재귀호출을 해서 구현할 수 있습니다
댓글을 작성하려면 로그인해야 합니다.
hanju0704 8년 전
분할정복을 이용하는건 알겠는데, 어떻게 구현해야될지 감이 안잡히네요.
문제를 보고
① '일단 2차원 배열을 선언 후, 내가 입력한 색종이 인풋을 저장해야겠다'
② 색종이를 4등분 분할 후, 각 종이마다 흰색이나 파란색으로 꽉차있는지 아닌지 검사하고
③ if(꽉차있을 시) --> 분할을 멈추고,
else --> ②를 반복한다.
이런 계획은 세워놓았는데, 구현한건 ①밖에 없네요.. 배열에 넣었는 놨는데 이거를
4등분하는 코드를 어떻게 작성해야할지도 모르겠네요. 사실 배열에 저장하는게 효율적인 방법일지도 의문이고요ㅠ
1시간정도 고민하다가 질문 올려봅니다. 이 문제를 어떻게 해결해나가야할까요?ㅠㅠ