색종이 붙이기

백준 17136번 : 색종이 붙이기(삼성 SW 역량 테스트)

17136번: 색종이 붙이기

 

 

그리디 + 백트래킹으로 해결할 수 있는 문제

 

나는 재귀를 이용하여 문제를 풀었다.

 

배열을 돌면서 큰 색종이부터 붙일 수 있는지 확인한다.(그리드 방식)

 

<1>현재 위치에서 5x5 크기의 색종이를 붙일 수 있으면 붙인다.

<2>다음 위치로 이동해서, 5x5 크기의 색종이를 붙일 수 있으면 붙인다.

...

<n-1>

<n>배열의 마지막 위치로 이동해서 5x5 크기의 색종이를 붙일 수 있으면 붙인다.

      마지막 위치에서 색종이 크기를 줄여가며 매 크기마다 붙일 수 있는지 확인한다.

      1x1 크기의 색종이까지 붙일 수 있는지 확인했으면, 다시 전 위치로 돌아간다.

 

<n-1>이 전에 5x5 색종이를 붙였었다면, 이번에는 4x4 색종이를 붙일 수 있는지 확인하고 붙인다.

        다시, 다음위치로 이동해서 5x5 크기부터 1x1 크기 색종이까지 붙여본다.

 

 

위 과정을 재귀를 사용하여 반복한다.

위 과정을 재귀로 반복하면서 매번 배열을 다 돌면, 사용한 총 색종이 개수가 최소인지 판정한다.

 

소스코드: