[BOJ] 백준 1010 다리놓기 (JAVA)

조합 기초 냠

📑 문제

백준 1010 다리 놓기

---

🌱 아이디어

본문에서 "다리는 서로 겹칠 수 없다." 라는 조건이 하나 붙는데 이번 문제의 키 포인트이다.
"다리는 서로 겹칠 수 없다." 라는 말은 곧 순서를 고려하지 않는다 는 말과 같다.

그림1번, 그림2번

두 그림은 같은 사이트에 다리를 잇는 경우의 수이다. 순서를 고려한다면 두 경우는 서로 다른 경우가 되어야 한다.

A, B, C != A, C, B 이 경우는 순서를 고려하기 때문에 요소가 같아도 순서가 달라 서로 다른 경우이다.

 

하지만 문제 조건 중 "다리는 서로 겹칠 수 없다." 를 성립하려면 위 두 그

림은 같은 경우의 수가 되어야 한다!

중복을 제거해야 하기 때문이다. 즉 A, B, C == A, C, B 이 성립되어야 중복이 제거가 되며 하나의 경우로 본다.

 

이 문제는 M개에서 N개를 뽑고 중복을 제거해야 하기 때문에

조합 공식을 사용해야 한다.

---

🌱 코드 및 풀이

nCr 조합 공식으로 풀어도 괜찮지만 조합공식 성질을 사용할 수 있다.

조합공식 성질 = n+1Cr+1 = nCr + nCr+1 을 이용하여 동적계획법으로 문제를 풀어보자!

dp배열 생성 후 1~30C1~30 모든 조합 경우를 dp배열에 저장한다.

 

dp[i][j] 를 구하기 위해선 왼쪽 항 "+1" 된 것을 오른쪽 항에 "+1"을 적용해 준다.

점화식 : dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

---

🌱 느낀 점

오랜만에 조합공식을 사용해 본 것 같아서 되게 헷갈렸었다ㅎㅎ

알고리즘 공부를 틈틈이 하면서 수학공식도 복습해야겠다

https://www.youtube.com/watch?v=42x7PSL0X7M -> 조합 공식을 맛있게 설명해 줌 👍