백준 14890번 경사로 (삼성 SW 역량테스트 기출문제)

문제 링크: https://www.acmicpc.net/problem/14890

사용한 알고리즘: 구현...?


 문제에서 경사로 설치가 가능한지 여부를 묻고 있습니다.

i번째에서 i+1번째로 갈 때, 경사로 설치시 제가 생각했던 점은 다음과 같습니다.
(1) 우선 같은 높이로 이동할 시, 같은 높이의 칸의 개수를 pre로 저장해줍니다.
(2) i -> i+1 이 낮은 곳에서 높은곳으로 이동일 시, 저장해 둔 pre 가 경사로를 설치하기에 필요한 개수(L) 이상인지 판단해 줍니다.
(3) i -> i+1 이 높은곳에서 낮은곳으로 이동일 시, 이를 일종의 갚아야할 빚으로 생각하고 bool로(HavetoPay) 체크했습니다. 이후 i+1 에서 계속 이동하면서 다음 높이 변화전까지의 같은 높이의 칸의 개수(pre)를 세고, 이 값이 설치하기에 필요한 개수(L) 이상인지 판단해 줍니다.
(4) 경사로 설치에 필요한 개수 L이 1로 주었을 시 주의해서 처리해 줍니다.

위의 4가지 생각을 갖고, 주어진 칸들의 그래프의 행과 열을 따로 판단해 주었습니다.
위에 써놓은 바와 같이 L=1일 때 많은 예외들이 발생하여 이를 끈기있게 생각해 주는 것이 포인트인 것 같습니다.