Algorithm/프로그래머스

[python] 프로그래머스 Lv 1 - 덧칠하기

떵호 2023. 9. 27. 20:02
728x90

🔗 문제 링크

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

📁 분류

그리디 구현

💡풀이

처음에 문제 예시를 보고 section의 차이 값을 구하고 m을 나누면 되겠다는 생각을 하고 제출했었는데 오답이었다.
8, 2, [2, 6] 를 반례로 볼 수 있다.

두 번째로 생각했던 방식은 n만큼 루프를 돌아 section에 i가 포함되어 있다면 answer에 1를 더해주고 i를 m만큼 더해주었다.

- 롤러가 벽에서 벗어나면 안 됩니다.
- 구역의 일부분만 포함되도록 칠하면 안 됩니다.

문제에 위와같은 설명이 있어 오답일거라 생각했지만 정답이었다. 😅

완벽한 가라는 진짜 아니겠는가? 😄

💻 코드

def solution(n, m, section):
    if m == 1:
        return len(section)

    answer = 0
    i = n
    while i > 0:
        if i in section:
            answer += 1
            i -= (m - 1)
        i -= 1

    return answer

# incorrect solution
# def solution(n, m, section):
#     if m == 1:
#         return len(section)
#     return int((max(section) - min(section) + 1) / m + 1)
728x90