프로그래머스 - Summer/Winter Coding(2019)(멀쩡한 사각형) / C++

*문제출처*

programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

문제 분석

가로(W), 세로(H) 길이의 직사각형이 주어진다.

1X1 크기의 정사각형으로 자르고 대각선을 그었을 때 

온전한 정사각형의 개수를 구해보자

 

처음 문제를 접했을 때 DP로 접근하였다.

하지만 4*10 정도 크기를 직접 구해보니 규칙이 없어서 이 방법은 포기하고 다른 방법을 강구하였다.

 

1차함수를 배운 사람이라면 쉽게 풀 수 있는 문제였지만, 문제 해결 과정을 도출해 내기까지가 어려웠다.

 

문제에서 주어진 사각판을 좌표평면이라 생각해보자.

좌측 아래와 우측 위를 두 점으로 잡고 일차함수를 표현한다.

각 x좌표에서 최대의 y값을 구해주면 멀쩡한 사각형의 개수가 나온다. 

위 아래가 대칭이므로 결과값에 *2를 해주면 답이다.

 

주의사항으로는 오버플로우 될 문제가 있어 작은 값을 큰값으로 나누어 주어야 한다.