말하는 컴공감자의 텃밭

문제가 너무 간단해 보였는데.. 진짜 한참 한참 걸린 문제다. 열받으면서 풀었는데 까먹을까봐 까먹을랑 말랑할때 정리한다. 먼저 지름길 갯수와, 거리가 주어진다. 지름길은 시작점과 끝점, 소모되는 시간이 주어지고 지름길이 오히려 더 길게되는 경우도 존재한다. 또한 고속도로이므로 역주행은 불가능하다. 150이 도착지점이면 정확히 150이어야 한다. 일반 고속도로의 경우 1당 1의 거리를 지닌다. 최솟값을 찾아야 하므로 효율이 좋은 지름길을 활용해서 도착점에 도달하면 되겠다. 초기에 이차원 배열을 통해 DP로 해결하려 접근했었다. 지름길을 통하면 이전에 대한 값과 비교해서 업데이트하고, 다시 그 이후의 길을 업데이트 하는식으로 말이다. 예제는 전부 옳게되었으나 문제가 발생했다. 지름길이 겹치는 경우였다. 로직..

사고싶은 카드의 개수가 주어지고, 이 카드를 가장 비싸게 사는 방식이다. 어떻게보면 베낭문제 같다. 단순하게 작은 카드뭉치부터 구매하면서 최대값을 찾아주면 되는 문제다. 처음 문제를 볼때는 공약수를 따져서 해야하나.. 했는데 간단하게 풀리는 문제였다. HTML 삽입 미리보기할 수 없는 소스

문제를 보자마자 조합? 이라고 생각했다. 출처: https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Ft1.daumcdn.net%2Fcfile%2Ftistory%2F2608F34059202A5833 왼쪽 다리놓을 포인트와 오른쪽 다리 놓을 포인트가 주어지고, 그 사이에서 다리 를 연결할 수 있는 경우의 수 이다. 다리는 겹쳐지는것이 허용되지 않는다. 그럼 뭐 순서가 필요없는 조합이자나요~ 다리 1개만 놓을건데. 다만 수가 굉장히 크기 때문에 Big Integer을 사용하거나, 모든 경우의 수를 저장해놓고 더하는 방식으로 진행했다. 조합에서 파스칼 삼각형을 사용하여 점화식을 적용했다. 출처 : https://namu.wiki..