7/23 TIL : 완전탐색

오늘은 한문제밖에 풀지 못하였다...

한번 늘어지니까 다시 회복하는게 너무 힘들구나아아

 

문제자체는 간단했다!

격자속에서, 기울어진 사각형 라인에 있는 숫자들의 합이 제일 큰경우를 찾으면 되었다.

 

처음 생각한건 무조건 사각형을 크게 만들면 되지 않을까? 였다.

즉 라인에 포함되는 숫자의 개수를 많게해서 해결하려고 하였다.

하지만 이런 모양의 격자를 생각해보면? 무조건 네모가 크다고, 숫자의 합이 크다는걸 보장할 수 없었다!

 

즉,,, 모든 크기에 대한 탐색을 진행했어야 했다.

 

그리고 생각할건, 기울어진 사각형을 어떻게 탐색할것인가? 였다.

일단 시작위치를 문제에서 정의해준것과 같이 생각하면,

왼쪽 위로 얼만큼 갈것인지, 오른쪽 위로 얼만큼 갈것인지만 정해주면 기울어진 사각형의 모양을 특정지어줄 수 있다.

 

그러면 얼만큼을 순회할것인가? 에 대한 생각은

이와같이, 격자의 각 모서리부분은 사각형의 시작부분이 될 수 없다.

즉 모서리를 제외한 부분만 순회를 돌리면 되었다.

 

크기는 어떻게 결정할것인가?

사각형은 격자의 범위를 벗어날 수 없으므로, 특정 위치에서의 최대크기가 결정된다.

이때의 최대크기를 왼쪽위로 얼만큼 올라갈 수 있는지, 오른쪽 위로 얼만큼 올라갈 수 있는지로 결정지어줄 수 있다.

즉 왼쪽위로 얼만큼 올라갈지, 오른쪽위로 얼만큼 올라갈지를 하나씩 줄여보면, 모든크기의 사각형에 대한 탐색을 진행해줄 수 있다.

 

---

흠,,., 그냥 평범한 완전탐색 문제였다.

뭔가 더 효율적으로 푸는 방법이 존재하겠지?