[2019 카카오 인턴십] 징검다리 건너기 (feat. PYTHON)

def solution(stones, k):
    answer, length = 0, len(stones)
    while True:
        loc = -1
        while True:
            if loc >= length: #건널수 있는 인원 추가
                answer += 1
                break
            flag = 0
            for i in range(1, k+1):
                if loc+i >= length: # 도착할 수 있으면
                    loc = length
                    flag = 1
                    break
                if stones[loc+i] > 0: #현재 위치에서 건널수 있는 디딤돌이 있으면
                    stones[loc+i] = stones[loc+i] - 1
                    loc = loc+i
                    flag = 1
                    break

            if flag == 0: # 건널 수 있는 돌이 없으면
                return answer

print(solution([2,4,5,3,2,1,4,2,5,1], 3))

정확성 : 100%

효율성 : 0%

 

4, 5번 마찬가지로 그냥 정답만 맞춘다고 풀다보니 효율성이 모두 실패한다.

dfs - 재귀랑, 반복문으로 푸는방법만 완벽하게 했어도...

 

문제해설 https://tech.kakao.com/2020/04/01/2019-internship-test/

[문제5 풀러 가기]