조합

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 처음에는 조합으로 풀면 되겠다 싶어서 풀었다. 계속 안 풀렸는데, 공집합인 경우도 있어서 depth 가 0보다 큰 경우에 카운팅 하도록 했다. 그리고 제출 후, 구글링을 해보니 다 나랑 다른 풀이로 풀었었다. 가장 이해가 되는 사진이 있어서 가져와보면, 재귀인 것은 똑같지만, 현재 값을 포함하는 경우와 포함하지 않는 경우로 트리 구조로 가져가서 풀었다. 두 풀이..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 전체 코드는 맨 마지막에 두었다. 문제를 풀기 전에 조합으로 팀을 나누고, 각 팀의 점수를 구한 뒤, 두 팀의 점수의 차 중 최솟값을 저장하면 되겠다 싶었다. 근데 우선 조합 구현을 순열로... 하고 있었고, 또 나는 조합 구현을 백트래킹으로 했고, 매개변수로 총 점수 합을 가져가는 식으로 구현했는데 다 풀고 찾아보니 조합때는 팀 편성만 담당하고, 마지막에 다 편성이 되면 그때 점수를 구하는 형태로 구현을 해둬서 나도..