31263. [Python]대한민국을 지키는 가장 긴 힘

1. 문제

 

https://www.acmicpc.net/problem/31263

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 1024MB
• Top-Down

 

3. 파이썬 코드

 

N = int(input())

number = input()
# 사람 수 체크
cnt = 0
# 인덱스 접근
index = N-1
# 인덱스 값이 0 보다 크거나 같을때 반복
while index >= 0:
    # 만약 현재 인덱스 -2 값이 0 보다 작은경우 사람 추가 후 탈출
    if index - 2 < 0:
        cnt += 1
        break
    # 현재 인덱스 기준으로 -2 까지 인덱스 값 정수로 변환
    day = int(number[index-2:index+1])
    # 그 정수값이 100보다 작은 경우 즉 010 이런 경우
    if day < 100:
        # 그 정수값의 길이가 한자리인 경우 인덱스 -1 외에는 -2
        if len(str(day)) < 2:
            index -= 1
        else:
            index -= 2
    # 100보다 큰 경우 인덱스 자리가 3자리
    else:
        # 만약 641 복무일수보다 큰 경우
        if day > 641:
            # 현재 일수를 나눠서 그 자리수 체크
            day_str = str(day)
            # 만약 자리수가 한자리면 인덱스 -1 두자리면 -2
            if int(day_str[1:]) < 10:
                index -= 1
            else:
                index -= 2
        # 641 이내의 경우 인덱스 -3
        else:
            index -= 3
    cnt += 1

print(cnt)

 

4. 문제를 풀고난 후 생각

 

• 인덱스 접근을 이용하여 문제해결에 접근했다.
• 처음엔 bottom-up 으로 접근하려다 010, 070, 707 이런 경우를 확인하기가 힘들어서 Top-down 방식으로 문제를 접근함.
• 현재 자리수가 몇자리인지에 따라서 인덱스 위치를 바꿔주는 것으로 문제를 해결함

 

5. 문제를 푸는데 도움이 되는 지식

 

• Top-Down(다이나믹 프로그래밍)