[boj 2085] 진법

문제 링크

 

입력으로 들어오는 숫자들을 쪼개가면서 진법으로 표현할 수 있는가 하는 문제입니다.

 

문제를 잘 읽어봐야 하는게, "불필요한 0이 사용되는 경우는 세지 않는다"의 의미가 헷갈려서 틀릴 수 있을 것 같습니다.

 

그 외에는, 뒷자리 숫자를 하나씩 늘려가며 경우의 수를 카운트했습니다.

 

import sys
input = sys.stdin.readline


def solve():
    string = input().rstrip()
    
    cnt = 0
    length = len(string)
    for idx in range(1, length):
        MOD = string[length-idx:length]
        
        if len(str(int(MOD))) != len(MOD) or int(MOD) == 0: continue
        
        MOD = int(MOD)
        
        dp = [0] * (length-idx)
        
        for i in range(1, length-idx+1):
            
            if len(str(int(string[:i]))) != len(string[:i]): continue
            
            if int(string[:i]) < MOD: dp[i-1] += 1

            if i == length-idx:
                cnt += dp[-1]
                continue
            
            for j in range(1, i+1):
                if len(str(int(string[i-j+1:i+1]))) == len(string[i-j+1:i+1]) and int(string[i-j+1:i+1]) < MOD:
                    dp[i] += dp[i-j]
                
    print(cnt)
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()