369 게임 3 (Large Test Case) - 파이썬 (DP)

사이트 링크 : https://codeup.kr/problem.php?id=3710&rid=0

 

문제는 아래와 같습니다.

문제

시작 수(a)와 마지막 수(b)가 입력되면 그 범위의 369게임에서 박수를 쳐야 될 횟수의 합을 출력하시오.

※ 369게임의 룰은 다음과 같다.

1. 숫자에 3이나 6이나 9가 들어가면 369 수에 해당된다.

2. 369 수에 해당될 경우 3이나 6이나 9가 들어간 개수만큼 박수를 친다. (예: 36은 박수를 두번 친다.)

3. 그 외의 숫자들은 박수를 치지 않는다.

아주 큰 범위의 테스트 데이터가 입력된다.

입력

• (1 <= a <= b <= 100,000,000)

출력

• 범위에서 박수를 친 횟수를 출력한다.

문제 해결 포인트 

• 회사에 일찍출근해서 해답 코드를 보지 않고 풀어본 문제입니다. (그래서 뿌듯합니다 ㅋㅋ )
  시간이 정말 많이 걸렸고 점화식이 떠오르지는 않은것 같습니다.
• 제 풀이가 최적화된 풀이라고 할수는 없겠지만 제가 설계한 DP 방식으로 푸는 방법을 공유드리겠습니다. 
• 아주 큰수이기 때문에 각 10 자리수 별로 끊어서 미리 박수 값을 저장해두고 불러오는 식으로 아이디어를 생각해두었습니다.
• 3333 이라면 3000 + 300 + 30 + 3 번의 박수 값을 모두 더며면 총 박수 값이 나오기 때문입니다. 
• 하지만 여기서 중요한점은 마지막이 3,6,9로 끝나는 수일경우 각 한자리수 내림 값에 박수를 한번 더 더해줘야합니다. 
• 3333이라면 3000 일때 333 번의 박수가 더해지기때문입니다. 
• [각자리수값,더 추가해하는값][3000,333],[300,33] ,[30,3],[3,0] 이렇게 됩니다. 
• 마지막으로 a<x<=b 값을 구하기 위해서는 1~a-1 값과 1~b 값을 구한뒤에 b-(a-1) 값을 해주면 됩니다 
• 아래 풀이과정을 정리해두었습니다 

1. 각 자리수 별로 DP 테이블을 생성하였습니다. (DP 테이블 점화식 dp[i] = dp[i-1]*7+(10**[i-1]+dp[i-1])*3)

자리수	0(0)	10(1~9)	100(1~99)	1000(1~999)	10000(1~9999)
박수친 횟수	0	3	60	900	180000

 

2. 그리고 각 박수를 반환하는 함수를 만들고 위에 작성된 요구사항에 따라 로직을 작성합니다.

 

복붙 가능코드 (아직 리팩도링이 덜되었습니다.)

a, b = map(int, input().split())
a -= 1
dp = [0 for _ in range(len(str(b))+2)]
dp[0] = 0
dp[1] = 3

for i in range(2, len(str(b))+2):
    result = dp[i-1]*7+(10**(i-1)+dp[i-1])*3
    dp[i] = result

# b 박수 - a 박수
def result_count(value) :
    count = 0
    value_list = str(value)
    value_len = len(value_list)
    for i, num in enumerate(value_list):
        for j in range(10):
            if j > int(num):
                break
            if j <= int(num)-1:
                if j in [3, 6, 9]:
                    m = value_list[i+1:]
                    count += 10**(value_len-1-i) + dp[value_len-1-i]
                else:
                    count += dp[value_len-1-i]
            else:
                if j in [3, 6, 9]:
                    m = value_list[i+1:]
                    if m == '':
                        m = 0
                    count += int(m)+1
            # count 확인용 print(count)
    return count

print(result_count(b)-result_count(a))

 

해당 문제는 계속 리뷰를 해서 코드를 정교화 해보는것도 좋은것 같습니다.