[Python] 백준 2591 숫자카드

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

2591번: 숫자카드

<알고리즘을 아직 안배워서, 관련내용은 없습니다>

 

문제분석

숫자가 주어지고, 숫자를 카드로 나타내는 것. (단, 카드는 1~34까지 무제한으로 있다)

문제자체는 너무쉽다. 21이면 21카드와 2와 1카드 두개로 나타낼 수 있으니, 가짓수는2개.

312면 3/1/2, 31/2, 3/12, 가짓수3개.

해결과정

문제를 보자마자 든 생각은, 재귀함수를 사용하자!였다. 너무 재귀함수를 사용하기 예쁜 그림이였다. 숫자하나빼고, 남은숫자로 함수또돌리고...숫자두개빼고, 함수또돌리고...이런 아이디어를 베이스로, 예시들을 경우의 수로 써봤는데.....

얼핏 배운 트리구조이다. 이를 바탕으로 적절히 예외 배치해서(비교할 숫자가 34를 넘는가?, 0을 비교할 때의 경우 등)

코드를 짰다.

#Sol.1 재귀함수(시간초과)
number=input()
intnumarr=[int(i) for i in number]
count=0
def auto_pop(arr):
    arr.pop(0)
    arr2=arr[:]
    return arr2
def main(arr):
    global count
    temparr=arr[:]
    if len(temparr)>=2:#2개이상일때,left right
        if temparr[0]*10+temparr[1]>34:#두개는안됨, 71번카드 없음
            main(auto_pop(temparr))
        elif temparr[0]==0:#앞자리가 0인경우, 05번카드는 없고, 0번카드도없음
            return
        elif temparr[1]==0:#뒷자리가 0인경우, 한개는안됨. 20이면 0번카드없음
            main(auto_pop(auto_pop(temparr)))
            return
        else:
            main(auto_pop(temparr))
            main(auto_pop(temparr))
    elif len(temparr)==1:
        if temparr[0]==0:
            return
        else:#빈배열이면 count+1해줌 알아서
            main(auto_pop(temparr))
    else:
        count+=1
main(intnumarr)
print(count)

그런데 제출해보니....

나중에 알게 된 사실인데, 재귀함수는 가독성은 좋지만 속도측면에서는 그다지 좋지 않다고 한다.

그래서 시간을 최소로 줄이기 위해, for문을 단 한개만 사용하기로 계획했다.

중요!

for문을 하나만 사용하는 방법은, 입력받는 숫자를 차례대로 읽어가며 경우의 수를 차례대로 더해가는 방법밖에 없다고 생각했다.

이를 코드로 나타내서, 정답을 맞췄다.

 

https://www.acmicpc.net/source/6414428

로그인

근데 이렇게 소스길이를 줄이는건 대체 어떤사람인걸까?

number=input()
intarr=[int(i) for i in number]
count=[0 for _ in range(len(intarr))]
for i in range(len(intarr)):
    if i==0 and intarr[i]==0:
        count[-1]=0
        break
    elif i==0 and intarr[i]!=0:#첫숫자가 0이아니면 count+1
        count[i]+=1
    elif i==1:#i가 1일때
        if intarr[1]==0:#i숫자0일때
            if 35>intarr[0]*10+intarr[1]>0:#앞이랑 만들어질때
                count[i]+=1
            else:#앞이랑 안만들어질때
                count[-1]=0
                break
        else:#i숫자0아닐때
            if 35>intarr[0]*10+intarr[1]>0:#앞이랑 만들어질때
                count[i]+=2
            else:#안만들어질때
                count[i]+=1
            
    elif i>1 and intarr[i]!=0:#i의 숫자가 0이 아닐때
        if intarr[i-1]==0:#i-1수가 0일때
            count[i]=count[i-1]
        elif intarr[i-1]!=0:#i-1수가 0이 아닐때
            if 35>intarr[i-1]*10+intarr[i]>0:#i과i-1로 카드한장나올때
                count[i]=count[i-2]*2+count[i-1]-count[i-2]
            else:#안나올때
                count[i]=count[i-1]
    elif i>1 and intarr[i]==0:#i의 숫자가 0일때
        if intarr[i-1]==0:#i-1수가 0일때
            count[-1]=0
            break
        elif intarr[i-1]!=0:#i-1수가 0이 아닐때
            if not (34>intarr[i-2]*10+intarr[i-1]>0):#i-2와i-1로 카드1장안만들어질때
                if not (34>intarr[i-1]*10+intarr[i]>0):#i-1과i로 카드못만들때
                    count[-1]=0
                    break
                elif 34>intarr[i-1]*10+intarr[i]>0:
                    count[i]=count[i-1]
            elif 34>intarr[i-2]*10+intarr[i-1]>0:#i-2와i-1로 카드1장 만들어질때
                if intarr[i-1]>3:#40 50이런거못만드니까 x
                    count[-1]=0
                    break             
                else:
                    count[i]=count[i-2]
print(count[-1])