1/26기록 - 백준 1010

오늘은 실버5 문제를 도전해 볼 수 있지 않을까 생각하면서 실버5의 맨처음 문제로 나와있는 1010번 다리놓기 문제를 들어가 보았다. 문제를 보자마자 고등학교 때 수학공부를 해두길 잘했다는 생각이 먼저 들었다 ㅋㅋㅋㅋ

 

 

문제는 위와 같다. 서쪽은 N, 동쪽은 M을 입력받아서 다리 개수를 출력하면 된다. N<=M이라는 조건이 핵심이고 서로 겹쳐질 수 없다는 조건도 핵심이다. 이 문제는 고등학교 확률에서 조합 문제와 같다. mCn 하면 사실상 끝인 문제!!!

겹쳐질 수 없다는 것에서 중복이 허용 되지 않음을 깨닫고 N<=M라면 이건 조합 뿐인 것이다.

 

mCn 을 구하기 위해서는 파스칼의 삼각형을 이해할 필요가 있다.

 

파스칼의 삼각형에 대해서 잘 소개하고 있는 블로그가 있어서 파스칼의 삼각형과 이항계수의 성질 : 네이버 블로그 (naver.com) 를 참고해서 위의 사진을 통해 mCn을 푸는 방식을 생각할 수 있었다.

 

nCr = n-1Cr-1 + n-1Cr 이라고 나타낼 수 있고, 이것은 이차원 배열을 통해서 인덱스만 조심해 준다면 어렵지 않게 해결이 가능하다.

 

 

이렇게 풀 수 있었다. 사실상 파스칼의 삼각형이 알고리즘 생각의 전부이기 때문에 오늘은 알고리즘 생각을 생략했다. 다만 이차원 배열 위에서 arr[i][i] = 1, arr[i][0] = 1, arr[i][1] = i 부분을 표현해 주었는데 계산 공식에서 인덱스를 넘어가는 경우가 발생할 수 있고 arr[i][1] = i 부분을 기재해 주면 조금이라도 더 빠르게 동작할 수 있지 않을까 하는 생각으로 간단한 계산은 미리 지정을 해 주었다.

 

 

문제 풀이 후 채점 현황을 살펴 보니 python으로 메소드를 사용해서 정말 간단하게 푼 풀이들도 많았고, 주로 mCn을 파스칼의 삼각형 보다는 반복문을 이용해서 순수 계산 공식으로 풀어준 풀이들도 많았다. 배열 때문에 더 오래걸렸을지도? 모르겠다... 반성!!!

 

1/26 기록 끝!!!!!!!!