구름 코딩테스트 Level 2: 장마 (구현 / with C)
먼저 가장 중요한 아이디어는 DP를 활용해서 장마가 시작한 위치 dp[s] += 1을 해주고, 장마가 끝난 위치 e에 대하여 dp[e + 1] -= 1을 해주고, 마지막에 0번 인덱스부터 맨 끝 인덱스까지 dp[i+1] += dp[i];를 실행해주면 어느 지역에 장마가 몇 번 왔는지 다 계산할 수 있다. 이를 3일 씩 끊어서 land라는 전체 data 배열에 저장해주는데, 똑같은 논리로 python으로 풀이하였을 때는 총 5개의 testcase에서 Timeout 판정이 났다. 같은 논리로 C언어로 풀이했을 때는 모든 testcase에 대하여 정상적으로 통과되었다.
C알고리즘
2023. 9. 29. 19:44
