[SWEA 코딩] 가능한 시험 점수 - PYTHON #3752

소스 코드

T = int(input())

for tc in range(1,1+T):

    # 점수 개수
    n = int(input())

    # 점수
    score = list(map(int,input().split()))

    # 방문 확인용
    board = [1]+[0]*(sum(score))

    # 만들어진 값 저장용
    store = [0]

    for q in score:

        # 깊은 복사
        temp = store[:]
        for w in temp:
            
            # 방문한적 없으면
            if board[q+w] == 0:
                
                # 방문하고
                board[q+w] = 1
                
                # 저장
                store.append(q+w)

    # 결과 값 = 만들어진 값의 길이
    res = len(store)

    print('#{} {}'.format(tc,res))

 

---

해결 방법

1. 조합의 개수를 구하는 문제

 

2. n의 최대 값이 100이므로 bfs 사용해서 접근 => 시간 초과

 

3. store라는 리스트를 만들어 그 안의 값들을 매번(score에서 값을 뽑아낼 때마다) 갱신하면서 진행함

---

느낀 점

깊은 복사의 필요성을 잊지 말자

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.