더블릿_종이 자르기(소트)

처음에 방향을 잘 못 잡아서 다소 몇 시간 헤맸다.

실전에서 이런 문제를 만나도 잘 풀기위해서는 어떤식의 사고 방식을 가져야 할지 모르겠다.

가로 * 세로 크기의 크기의 색종이에 

가로, 세로 마다 줄이 쳐져 있고, (배열이라는 소리)

자르는 인덱스가 주어진다. 

자르는 색종이들중의 크기 중 가장 최대의 것을 찾는 문제이다. 

문제풀이)

처음에는 장애물을 주어지고 dfs를 수행 할려고 했다. 세 시간을 생각해보아도 명확하게 코딩 할 수 있는 방법이

떠오르지 않았다. 

사각형의 넓이에 범위에 대해서 부분, 부분 나눌 수 있는 방법에 대 해서 생각 해보았다. 

좋은 아이디어가 발견됐다. 

예제를 통해서 설명하면

가로 10, 세로 8

가로 커팅이 2, 3번째 선이라고 입력으로 들어 오고,

세로 커팅이 4번째 선이라고 입력으로 들어온다면,

잘린 세로의 선들을 나열하면 0~2까지 선, 2~3까지의 선, 3~8까지의 선 이렇게 3개다.

잘린 가로의 선들을 나열하면 0~4까지 선, 4~10까지의 선 이렇게 2개다.

이 모든 선들을 가로 * 세로 구하면 모든 사각형의 넓이를 구할 수 있게 되는 것이다.

즉!

결국 잘린 선 중에 가로의 최대 길이,

세로의 최대 길이를 구해서 둘이 곱해주면 최대값을 구할 수 있다는 것이다.

간단하게 생각해서 각각의 사각형의 가로 세로 길이를 구해서 넓이를 구하려고 하다보면 내가 푼 아이디어까지 도달할 수 있게 된다.