펭로그

틀림 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667// BOJ 2110 공유기 설치#include using namespace std; struct node { int from; int to; // 우선순위큐 comparator bool operator num >> ap; int input, s = 1000000000, e = 1; vector house(1000000001, false); while (num--) { cin >> input; house[input] = true; s = min(s, input); e = max(..

문제 링크 : https://boj.kr/2293 1234567891011121314151617181920212223242526272829303132// BOJ 2293 동전1#include using namespace std; int dp[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", stdin); int num, result; cin >> num >> result; vector coin(num + 1); vector dp(result + 1, 0); for (int i = 1; i > coin[i]; dp[0] = 1; for (int cn :..

문제링크 : https://boj.kr/1463 DP를 사용하면 이전 단계의 계산 결과를 그대로 활용할 수 있는 문제이다.문제에서 힌트로 주어진 10을 연산하는 방법을 생각해보면10 -> 5 -> 4 -> 2 -> 110 -> 9 -> 3 -> 1이런 방법이 나올 수 있을 것이다.10이라는 숫자는 바로 2로 나눌 수 있는 숫자이지만 -1을 한 후에 연산하면 횟수가 더 적은 것을 확인할 수 있다.따라서, 어떤 숫자가 2나 3으로 나눌 수 있을 지라도 -1을 했을 때와 비교한 후 최소 횟수가 어느쪽인지를 취하면 문제를 풀 수 있게 된다. 1을 뺀 후에 연산하는 방법이 어떤 경우에도 허용이 되기 때문에 먼저 1을 빼서 연산한 횟수를 계산한다.현재 숫자에서 1을 뺀 연산은 이전 단계에서 이미 연산이 되었기 때문..

문제링크 : https://boj.kr/2193 이친수의 조건1. 0으로 시작하지 않는다.2. 1이 두번 연속으로 나오지 않는다. 이 조건을 만족하려면 반드시 2자리 이상의 이친수는 10으로 시작하게 된다.그리고 10의 뒷부분 역시 이친수의 조건을 만족해야 이친수가 될 수 있다. DP를 이용하면 간단하게 풀린다.5자리 이친수의 경우 아래와 같이 표현할 수 있다.10+3자리 이친수100+2자리 이친수1000+1자리 이친수10000+0자리 이친수(사실 존재하지 않음) 이를 DP 식으로 표현하면 다음과 같다. 이 식에 따라 아래와 같이 풀어주면 된다.여기서 주의할 점은 47번째 숫자의 값이 2,971,215,073이 되어 int 표현 범위를 초과하게 된다.반드시 long long 타입으로 선언해주어야 한다. ..

문제링크 : https://boj.kr/14501 12345678910111213141516171819202122232425262728293031// BOJ 14501 퇴사#include using namespace std; int max(int a, int b) { return a > b ? a : b;} int dp[17]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("../input.txt", "r", stdin); int num, day, pay; cin >> num; for (int i = 1; i > day >> pay; dp[i + 1] = max(dp[i], dp[i + 1]..