[Week of Line Sweep] BOJ 14465

이번 문제는 solved.ac 기준으로 Tier가 좀 낮을 걸로 선택해서 풀어봤다.

 

문제를 다 읽고 생각난 건..

'아 이거 이해는 다 했는데.. 중간에 있는 것들을 하나씩 빼야 되나?'

'그러면 경우의 수가 너무 많아져서 시간 초과가 날 것 같은데..'

'아무리 봐도 모르겠다. 해설을 찾아보자.' (velog.io/@ruz/BOJ-14465)

 

기-승-전-해설로 구글링 시작.

생각보다 매우 간단쓰한 해결책이 있었다.

 

1번부터 K의 길이를 갖는 자(ruler)를 대봐서

그 안에서 망가진 신호등의 개수를 세면 되는 것이다.

아래 그림을 참조하면 이해하기가 더 쉬울 것이다.

그래서 처음에는 1번부터 N-K까지 순회를 돌고 (index : i)

그 안에서 다시 i번부터 i+K까지 순회를 돌아서 값을 구했다.

(신호등의 배열을 Boolean으로 설정하고 망가진 경우 False, 정상인 경우 True를 넣어주었다.)

 

그리고 제출했는데.. 이런

TLE(Time Limit Exceeded)가 발생했다.

다시 문제를 보니 N이 100,000이 최대 값이라서

N^2 = 10,000,000,000이라 시간 초과가 날 수밖에 없는 로직이었다.

 

그래서 생각을 해보니

맨 처음에 1부터 K까지를 구하고

그다음부터는 그냥 1씩 index를 증가시키면서

가장 왼쪽의 값을 빼고, 가장 오른쪽의 값을 더해주면 TLE가 발생하지 않을 것 같아 그리 구현을 했다.

(신호등의 배열을 int로 설정하고 망가진 경우 1, 정상인 경우 0을 넣어주었다.)

그랬더니 문제없이 통과!

 

첫 아이디어는 해설을 참조했지만

TLE에 대한 부분은 내가 스스로 해결해서 매우 뿌듯한 풀이였다.

 

이렇게 경험을 쌓다 보면

첫 문제풀이 아이디어도 내가 내서 풀어낼 수 있을 날이 오겠지.