[백준 10265] MT

[백준 10265 : MT ]

꼭 이런친구들 있다...

사람 수 N과 버스에 태울 수 있는 사람 수 K가 주어지고 (1<=K<=N<=1000) 각 사람(Xi[n])들의 연관성이 주어진다.
의견을 해치치않고 최대한 태울 수 있는 인원 수를 출력하는 문제인데 
나는 dp+dfs방식으로 풀었다.

개인과 연관된 사람들의 묶음이 필요하다고 느껴 dfs를 썼고
0번 사람을 태웠을때 누가 더 탈 수 있는지 1번 사람을 태웠을 때 누가 더 탈 수 있는지 모든 정보가 필요해서 메모리제이션을 이용해 최대 태울 수 있는 인원 수를 구했다.

학생들은 서로 방향성을 가진 그래프로 표현이된다.
그러므로 벡터에 넣어줄때 일방향으로만 넣어주면된다.

DP로 풀 것이므로 메모이제이션할 배열의 크기 설정을 해준다.
한 학생의 묶음은 1000명까지 가능하다.
학생은 총 1000명까지 된다. 그러므로 1000x1000으로 잡아준다.

그리고 이제 1번 학생부터 본다. 1번 학생과 같이 타야하는 학생들을 구해준다.
만약 k보다 작거나 같다면? 다음 인덱스로 갈 수 있다.
이때 태웠을때와 안태웠을때로 갈라지면서 재귀를 들어간다.
그럼
재귀(다음 인덱스, 현재까지 태운 학생) 와
재귀(다음 인덱스, 현재까지 태운학생+방금 계산한 묶음)
이렇게 들어갈 수 있다.
재귀의 종료시점은 인덱스가 N에 도달했을때 이다.

이런식으로 풀어줬는데 한번 DP의 깊이에 들어갈때마다 태울지 말지를 결정하는 부분이
처음에 헷갈려서 초반에 난감했던 문제였다.

냅쌕알고리즘을 공부하고 왔더니 다시 봤던 문제인데
먼저 냅쌕을 풀고 온다면 쉽게 풀 수 있는 문제다.