dp9 1943 - 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 과정 입력을 받으면서 가능한 코인의 경우를 true로 바꿔줍니다. coins를 모두 돌며 sum/2부터 역순으로 진행합니다. 이전 idx를 기준으로 탐색을 진행하기 때문에 탑다운 방식으로 진행합니다. 정답 이하인 경우만 진행하면 됩니다. 코드 #include #include using namespace std; vector coins; bool dp[100001]; int N; in.. 2023. 7. 25. 2098 - 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 주의할 점 최대 값을 주고 돌리는 경우 방문을 해서 최대 값인지 아닌지를 알 수가 없어 무한루프가 발생한다. -1을 준 뒤 방문을 구분하자. 코드 #include #include #include #include using namespace std; typedef pair PII; int N; vector ways[16]; int dp[16][1 >N; for(.. 2023. 7. 18. [Level 3] - 스티커 모으기2 https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각해 보기 최대값을 찾아야 하므로 dp로 진행을 하자. 현재 스티커가 들어간다는 가정하에 dp[i] = max(dp[i-2]+sticker[i], dp[i-1])가 성립한다. 맨 처음 스티커가 들어가는 경우 dp[i][0] 안들어 가는 경우 dp[i][1]로 진행하자.(맨 뒷 부분이 들어가면 안되기에 구분을 한다.) 코드 #include #include using namespace std; in.. 2023. 7. 10. 9527 - 1의 개수 세기 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 과정 2진수로 생각을 해보자. 11111(2)을 기준으로 보면 00000 -> 00001 -> 00010 -> ... 으로 진행 되게 된다. 1자리 -> 1 1개, 2자리 -> 10 11 01 4개 맨 앞 1의 경우 이전 자리 경우의 수 -> 2^n, 맨 앞이 0, 1 2가지의 경우 이므로 dp[n-1] * 2로 진행하게 된다. 단순 공식으로 변환해보면 dp[n] = dp.. 2023. 7. 7. 이전 1 2 3 다음
