https://www.acmicpc.net/problem/27519 1 ~ n 까지의 정수를 소수의 합으로 표현하는 방법의 개수를 구하는 문제이다.예를 들어 8을 표현하면1) 2 + 2 + 2 + 22) 2 + 3 + 33) 3 + 5이렇게 3가지가 존재한다.여기서 중요한 점은 3 + 5와 5 + 3을 같은 방법으로 고려한다는 점이다.이는 i == 8인 경우에 dp[i] = dp[i - 3] + dp[i - 5]가 아니라는 것을 의미한다. 이를 위해서 우선 2만으로 만들 수 있는 숫자를 카운트한다.dp[0] = 1로 선언해주고dp[i] = dp[i - 2] 로 선언해주면 i == 2인 경우 dp[2] = 1을, i == 4인 경우 dp[4] == dp[2] == 1을 저장하는데,이는 곧 4를 만들기 위해..
분류 전체보기
https://www.acmicpc.net/problem/27315 24년 2학기 문제해결기법 수업 11주차 B번에 나온 문제와 유사한 문제다만 데이터가 있는 경우 구현 난이도에 관계 없이 풀 수 있다는 부분만 잘 생각해주면 된다. 우선 가장 간단한 생각은 구현 난이도 - HP(구현 능력)의 총합이 작을수록 좋은 결과이므로 구현 난이도에 따른 오름차순 정렬을 하면 좋겠다고 생각했다.다만 문제는 구현 난이도가 낮지만 아이디어가 높은 경우에는 문제를 해결할 수 없고,HD는 높지만 구현 난이도가 조금 높은 문제를 여러 문제 해결한 이후 높아진 HD에 따라 구현 난이도가 낮아진 문제를 해결할 수도 있는 가능성이 존재한다.또한, 데이터가 존재한다면 구현 난이도는 고려할 대상이 아니므로 0점을 부여해도 무방하고,에..
https://www.acmicpc.net/problem/23820 mex(S)는 S에 포함되지 않은 가장 작은 음이 아닌 정수이다.이 때 mex({ai * aj})를 구하는 문제이다. ai의 범위는 200만 이하의 음이 아닌 정수이고, 곱으로 집합의 원소를 결정하므로 절대로 나올 수 없는 가장 작은 소수는 계산해보니 2000003이다.그러므로 어떤 수를 곱하던지 상관 없이 2000003을 넘어간다면 즉시 종료하면 되고,모든 가능한 곱을 다 계산한 이후 0 ~ 2000003까지 나오지 않은 정수를 파악하면 된다. 12345678910111213141516171819202122232425262728293031#include iostream>#include vector>#include algorithm..
https://www.acmicpc.net/problem/10986 풀면서 그렇게 어려운 문제는 아니었으나, 오랜만에 보니 잘 기억이 안나서 정리 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하라는 문제인데,보자마자 배열에 나머지만을 저장해도 되겠다는 생각이 들었다.또한, 연속된 구간의 개수이므로 누적합을 이용해야지 시간초과를 방지하지 않을까라는 생각도 들었다.12345678910111213141516171819#include iostream>using namespace std;int sum[1000001], cnt[1001];int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ..
이런 문구가 뜬다 cmd 창에 diskpart를 입력해주고 disk 1의 크기가 usb 크기처럼 보인다. 이후 attributes disk clear readonly를 입력해주면 된다.
