programmers- lv.1 (덧칠하기)

문제링크: 덧칠하기

✍🏻 Information

	content
언어	python
난이도	⭐️⭐️
풀이시간	25분
제출횟수	2
인터넷검색유무	no

🍒 My Code

def solution(n, m, section):
    answer = 0
    point = section[0]
    for s in range(1,len(section)):
        if point+m<=section[s]:
            answer+=1
            point=section[s]
    """
    point = section[0]
    MAX = max(section)
    while point<=MAX:
        point+=m
        answer+=1
    """    
    return answer+1

💡 What I learned

• 처음에는 주석에 있는 것처럼 풀이하였다. 그러면 내가 추가한 test case 중 2번째에서 4로 계산한다. point를 1->2->4로 옮겨주어야하는데 1->2->3->4로 옮기기 때문.
  

• 이를 해결하기 위해 만약 다음 칠할 section이 현재 칠한게 끝난 지점보다 더 뒤일 경우(뒤에 건너 뛰어도 되는 부분이 있는 경우) point를 다음 section으로 옮겨주도록 코드를 작성하였다.

• 1 ≤ m ≤ n ≤ 100,000이고 1 ≤ section의 길이 ≤ n이기 때문에 이중 for문을 쓰거나하면 시간초과가 날것이라 위 방법(point를 옮겨주는 방식)으로 풀이하였다.