조합2 [Kotlin] 백준 12785 : 토쟁이의 등굣길 문제 링크 12785번: 토쟁이의 등굣길 인하대학교에 다니는 토쟁이는 y축과 평행한 w개의 도로, x축과 평행한 h개의 도로가 있는 도시에 살고 있다. 토쟁이의 집은 이 도시의 맨 왼쪽 아래에 위치하며 좌표로는 (1, 1)로 표시할 수 있다. www.acmicpc.net 문제 해설 최단 경로 문제다. 토쟁이의 집부터 토스트 가게까지의 최단경로와 토스트 가게부터 학교까지의 최단경로를 구하여 두 값을 곱한 결과를 1,000,007로 나눈 나머지를 출력하면 된다. 최단 경로 문제는 조합으로 해결할 수 있다. 위와 같은 모양의 지도가 있을 때 start에서 end까지 이동하는 최단 경로의 수는 →오른쪽 5개와 ↑위쪽 3개로 이루어진 집합에서 5개의 →오른쪽이나 3개의 ↑위쪽을 뽑는 경우의 수가 된다. 따라서 위.. 2022. 12. 14. [Kotlin] 백준 1010 : 다리 놓기 문제 링크 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 해설 문제의 결론만 따지자면 \( _{m}\mathrm{C}_{n}\)을 구하는 문제다. 강 서쪽의 n개의 사이트를 모두 선택하여 강 동쪽의 임의의 m개의 사이트에 하나씩 연결해야한다. n ≤ m이므로 m개 중 n개를 선택하는 경우의 수와 같다는 것을 알 수 있다. 여기서 다리가 겹쳐질 수 없다는 조건이 있는데 이에 대한 예시는 다음 그림과 같은 두 경우를 들어보겠다. 각 경우를 배열로 나타내면 첫번째는 [1, 2, 3], 두번째는 [2, 3, .. 2022. 11. 24. 이전 1 다음
