생각금액이 다른 동전 N개와 원하는 금액 K가 주어진다. N개의 동전들을 최소한으로 사용하여 K를 만들 때 그 최소한의 동전수를 출력하여라. 만들 수 없을 경우 -1을 출력한다. 처음 생각DFS를 통해 풀이를 하였으나 시간 초과가 나왔다. 다음 생각이런 동전류의 문제는 이전 값을 계산해서 나아가는 다이나믹 프로그래밍(DP) 방식을 사용해서 푸는 경우가 많으므로 DP로 접근하였다. 다다음 생각동전의 숫자를 구하는 것이므로 이 금액을 만들 수 있나의 개수를 파악하면서 가는것이 아닌 이 금액을 몇 개의 동전으로 만들 수 있나를 파악하면서 가도록 진행하였다. 자세한 설명은 코드상에 주석으로 달아 놓았습니다.다다다음 생각따라서 DP를 구하기에 앞서 DP에 해당 Index 1~K 일 때, 주어진 동전의 배수를 미리..
생각처음 생각L시간 이하로 이동이 가능한 모든 경로를 살펴봐야 하므로 BFS 탐색을 선택하였다. 다음 생각data inner class를 하나 만들어 cnt를 통해 해당 cnt가 L을 넘어설경우 탐색을 종료하였다. 탐색을 하는 동안 queue의 아이템을 꺼낼 때마다 결과값을 +1 시켜주었다. 다다음 생각탐색은 총 7개의 Case로 나누어서 해당 Case에 알맞게 좌표 이동을 할 수 있도록 하였다. 다다다음 생각위와 같이 진행을 하니 결과값이 다르게 나오는 것을 볼 수 있었다. 무엇이 문제였을까? 방안1) 문제는 바로 무조건 다음 파이프로 이동한 것이었다.▶ 예를들어 '+' 모양의 파이프에서 왼쪽으로 이동하였을 때, 이동한 곳의 파이프 모양이 'ㅣ' 일 경우에는 이동이 되어서는 안된다. 따라서 이동할 수 ..
생각2차 배열로 주어진 등산로에서 가장 긴 등산로를 찾는 문제이다. 등산로는 높은 숫자에서 낮은 숫자로만 이동할 수 있다. 이 때, K 값이 주어지는데 이 K는 한 등산로를 만들 때 한 번만 사용할 수 있는 지형을 파괴할 수 있는 높이이다. 만약 처음 등산로가 9로 시작하면 근처에 있는 9로는 못가게되지만 파괴를 한 번 할 수 있는 기회를 사용해서 K=1 일 경우 다음 9를 8로 만들어서 진행 할 수 있다. 처음 생각우선 List를 이용해서 처음에 등산로의 숫자를 입력받는 부분에서 가장 높은 숫자가 나오면 List에 추가해 주어 등산로의 출발 경로를 설정하였다.▶ Max가 바뀔 경우 List를 초기화 하여 이전 출발 경로들을 없애고 새로 넣어준다. 다음 생각등산로의 출발 점을 하나씩 DFS 탐색하면서 가..
- Total
- Today
- Yesterday