코딩못하는사람

https://www.acmicpc.net/problem/22115 22115번: 창영이와 커피 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. www.acmicpc.net 1.접근 백트래킹으로 생각하고 풀었다가 시간초과를 맞았다. k가 커질 수록 시간이 급격히 늘어나는 코드였다. 얻어야하는 카페인양과 커피들의 카페인양을 보고 냅색문제처럼 최적 부분 구조로 나누어 풀 수 있다는걸 알았다. 2.풀이 각 커피에 카페인이 1, 2, 3, 4, 5 가 들어있고 마셔야하는 카페인이 15라고 가정해보자. 만약 5가 커피의 최소 개수를 위해 꼭 마셔야하는 커피라면 15에서 5를 뺀 10의 카페인을 1,2,3,4커피를 가지고 마시는 경우 +1이 최소 개수의 커피를 마시는..

https://www.acmicpc.net/problem/1086 1.접근 방문했던곳들의 상태를 표기하기 쉽도록 비트마스크를 사용하고 n이 15일때 15!로 숫자가 크므로 DP를 사용해줘야 한다. 2.풀이 분모를 N!,분자를 k로 나눠떨어지는 경우의 수로 두는 문제이다.그래서 나는 DP배열을 DP[방문한곳][현재 나머지]로 만들고 DP[방문한곳][현재 나머지]=방문할 수 있는 곳들에서의 경우의 수 합 으로 점화식을 만들었다.그렇게 DFS를 사용하여 방문했던 곳이 나오면 그대로 값을 리턴하고 만약 모든 곳을 방문하고 나머지가 0일 때는 1을 리턴해주는 함수DFS를 만들었다. 나머지는 (이번에 추가하는 숫자*10**현재수의 길이) 현재 나머지를 더하고 k로 나눠주면서 저장하면 된다. DP를 0으로 초기화 해..