#3752. 가능한 시험 점수

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE

SW Expert Academy

 

n개의 수가 주어지고 n개만큼 점수를 입력한다.

예를들어 n=3이면

2 3 5를 입력하고 이때 나올 수 있는 모든 점수의 경우의 수를 출력하는 문제이다.

 

이때 가능한 모든 점수는

0 2 3 5 7 8 10 총 7가지이다.

 

이문제를 푸는 방법은 다음과 같다.

 

맨 처음 만들 수 있는 점수는 아무것도 선택하지 않는 0점은 모든 경우에서 동일하다.

 

그 후 2점을 선택하면 만들 수 있는 모든 경우는 0,1,2까지 인데 1점은 만들 수 있는 점수에 포함되지 않으므로 생략한다. 한편 만들 수 있는 점수에 0점이 있으므로 0점을 활용할 수 있다.

따라서 0점과 2점을 만들 수 있고 독립적으로 2점은 항상 true로 score배열에 추가시켜주어야 한다.

다음으로 3점을 보자. 이제 맥시멈 5점까지 만들 수 있다. 그 중 이미 만들어져 있는 수는 0,2이 이므로 3점을 합한 점수인 3,5점 까지 만들 수 있다. 이떄도 마찬가지로 합한 수에 3점이 추가가 안 되어 있을 수도 있으므로 독립적으로 3점을 score배열에 추가 시켜야 한다. 이와 같은 과정을 반복하게 되면 가능한 모든 경우의 수를 구할 수 있게 된다.

 

소스코드