문제 출처 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 알고리즘 분류최단 거리 알고리즘 풀이dp[A][B]면 A보다 B가 키가 더 크다는 것이고, dp[B][A]면 A보다 B가 키가 더 작다는 뜻이다.M가지의 키 정보를 기록하고 플로이드-워셜 알고리즘을 사용하여 N명 전체의 키의 상관관계를 기록한다.i번째 행에서는 i번째 사람보다 키가 큰 것이 확실하다면 1 이상의 숫자가 기록될 것이고, 그게 아니라면 -1일 것이다.i번째 열에서는 i번째 사람보다 키가 작은 것이 확실하다면 1 이상의 숫자가 기록될 것이고, 그게 아니라면 -1일 것이다.이를 이용해서 i번째 사람보다 키가 큰 사람과 키가 작은 사람의 수를 구할 ..

문제 출처 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 분류 다이나믹 프로그래밍 풀이 점수의 개수가 총 100개이기 때문에, 경우의 수는 2^100가지이므로 백트래킹으로는 풀 수 없다. 따라서 DP로 해결해야 한다. 먼저 0점은 처음부터 가능하므로 DP[0] = true로 초기화한다. 그리고 다음 점수를 입력받으면 현재 점수의 Index * 100(== i)점부터 DP[i]가 true라면 DP[i + 점수] 역시 true가 된다. 첫 번째 테스트 케이스를 보자면, 처음에 2점을 입력받았으므로 DP[0 + 2]는 true가 된다. 그리고 다음 3점을 입력받았으므로 DP[2 + 3], DP[0 + 3]..