백준 17136 색종이 붙이기 풀이, 코드 (파이썬) 구현문제 / 삼성 A형 기출

코드만 궁금한 분은 깃허브 링크 눌러주세요!

GitHub - Rhyankwon/algorithms

 

문제 설명ㄱㄱ

17136번: 색종이 붙이기

 

문제 풀이

 

1. (0, 0) 부분부터 (9,9) 부분까지 모두 각각 1x1 부터 5x5 까지 색종이가 들어갈 수 있는지 확인해본다. 

2. 이 때, 당연히 각 부분이 1인 경우에 대해서만 색종이를 대입해보고 만일 0이면 다음 부분 (x+1, y)혹은 (x, y+1)로 넘어간다. 나는 x+1, y부분으로 넘기는 식으로 했는데 이론적으론 아무렇게나 해도 상관x

3. 이 때, 각 부분마다 들어갈 수 있는 색종이 종류가 여러개일 수 있으므로 재귀를 통해 하나의 가능한 색종이에 대해 탐색이 끝나면, 탐색시 색종이를 덮은 부분을 1 -> 0으로 모두 바꿨다가 다시 0 -> 1로 해서 새로운 색종이로 탐색한다.

4. 매번 탐색이 끝나는 경우마다 (9째 열 혹은 행까지 끝나는 경우마다) 색종이 갯수를 업데이트한다.

여기에서 가장 중요한 부분은 3번인 것 같은데, 이 부분을 코드로 보면 아래와 같다.

                for k in range(i+1):
                    for j in range(i+1):
                        grid[x+k][y+j] = 0
                paper[i] += 1
                func(x+i+1, y, cnt+1)
                paper[i] -= 1
                for k in range(i+1):
                    for j in range(i+1):
                        grid[x+k][y+j] = 1

전체 코드를 보고싶으면 맨 위 깃허브 링크를 누르면 된다.

 

 

 

---------------------------------------------------------------------------------------------

1. 처음에는 큰 색종이부터 하나씩 넣어봐야하는 것 같아서 그렇게 문제를 풀다가 웬지.. 예외처리하기가 상당히 까다로울 것 같아서 빠르게 gg쳤다.

 

2. 그래서 전부 다 해봐야하나? 하고 다른 풀이를 검색해봤는데 그냥 다 해봐야된다고 해서.. 해당 풀이를 조금 참고해 문제를 풀었다. 근데 문제를 풀고나서 보니까 코드가 완전히 똑같아졌다.

https://chldkato.tistory.com/167

백준 17136 색종이 붙이기 (파이썬)

위 링크를 참고했다.

 

3. 확실히 삼성 구현문제.. 어렵다. 귀찮고 까다롭고 어렵다. 정말 이렇게 푸는게 맞아? 싶으면 맞다. 삼성..준비 열심히해야겠다.