펭로그

문제링크 : 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]..

문제링크 : https://boj.kr/11052 123456789101112131415161718192021222324252627282930// BOJ 11052 붕어빵 판매하기#include using namespace std; int max(int a, int b) { return a > b ? a : b;} int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("../input.txt", "r", stdin); int num; cin >> num; vector price(num + 1); // 개당 가격 vector dp(num + 1); // 최대 값 저장 for (int i = 1; i >..

문제 링크 : https://boj.kr/2156 이 문제에서는 연속된 인접 포도주가 최대 2잔까지 허용된다.이 문제에서의 핵심은 포도주를 마시기 위해선 인접한 최대 2개의 노드를 비교했을때 마신 포도주의 위치가 2 이하여야 하는 것이다.포도주를 마신 위치를 1로 하고 안 마신 위치를 0으로 표현하였다. 현재 위치를 기준으로 그 이전 단계를 계산한다면 아래의 경우를 생각할 수 있다.1. 현재 포도주를 먹지 않았을 경우 - 그 앞에 어떤 경우가 와도 상관 없다. 마신경우, 최대 2개까지만 허용 (0+0, 1+0, 1+1+0)2. 현재 포도주를 먹었을 경우 - 바로 전 포도주를 먹지 않았을 수도 있다. (0+1) - 바로 전(-1) 포도주를 먹었다면 반드시 그 이전(-2) 포도주는 먹지 않았어야 한다. (0..

문제 링크 : https://boj.kr/1149 어떤 집을 R, G, B 중 하나로 색칠할 때 인접한 이웃 끼리는 서로 색이 겹치면 안된다. 한 집을 R로 선택하게 되면 그 다음에 올 수 있는 이웃의 값은 G, B 중에 하나만 올 수 있게 된다.그 중에 G를 선택했다면 그 다음 값은 R, B 중에 선택해야 한다.R, G, B의 3가지 값 중에서 하나를 선택하면 그 값을 제외한 2가지를 선택할 수 있다.2가지 선택값 중에서 하나를 선택하면 그 뒤에는 또 2가지를 선택할 수 있는 경우의 수가 주어진다.이 과정을 반복하면 3*2*2*2* .....가지의 경우의 수가 나오며 일반항으로 고쳐보면 3*2^(N-1)가지의 경우를 계산해야 함을 알 수 있다.이를 빅-오 표기법으로 바꿔보면 O(2^N)임을 알 수 있다..

문제 링크 : https://boj.kr/1932 입력이 위 그림과 같이 정삼각형 형태의 피라미드의 형태로 주어진다.이 형태를 어떻게 입력받아야 할까? 하고 고민을 해봤다.첫줄부터 인덱스를 메겨서12 34 5 67 8 9 1011 12 13 14 15이런 형태로 각 줄의 첫 인덱스들이 1, 2, 4, 7, 11 이런 식으로 늘어나는 계차수열 형태로 입력받아야 하는가? 하고 고민도 해봤다. 하지만 입력을 보니 그냥 이런 형태 그대로 입력 받아도 계산하는데는 문제 없겠구나 싶었다.따라서, N*N 형태의 일반 매트릭스 형태로 입력받고 모든 노드를 0으로 초기화 시킨 상태에서 계산하도록 하였다. 이 문제는 재귀로 풀게되면 엄청난 연산 횟수로 시간초과를 발생시킬 수 있는 문제이다.상위 단계에 있는 인접 노드의 값..

문제 링크 : https://boj.kr/1834 이 문제는 막상 해보니 어렵지 않았다.종이에 직접 써보면서 규칙을 찾으니 쉽게 점화식을 찾을 수 있었다. [N = 젯수 일 때, 피젯수(몫,나머지) 순서]N = 1 일 때, 존재하지 않음N = 2 일 때, 3(1,1)N = 3 일 때, 4(1,1) 8(2,2)N = 4 일 때, 5(1,1) 10(2,2) 15(3,3)N = 5 일 때, 6(1,1) 12(2,2) 18(3,3) 24(4,4) 벌써부터 규칙이 보인다.1. 몫과 나머지가 같은 수들은 N+1의 배수들2. 배수의 갯수는 N-1개점화식을 구해보면 (N + 1) * i 가 된다. 단, 이 문제는 입력 최대 값이 2,000,000이기 때문에 최대로 올 수 있는 값은 sigma(i=1~1,999,999)..

문제 링크 : https://boj.kr/1978 이 문제는 에라토스테네스의 체를 이용하여 소수 리스트를 미리 구한다음 계산하면 쉽게 답을 찾을 수 있다.입력 최대값이 1000밖에 안되기 때문에 그냥 1000까지 미리 소수를 구하는 편이 빠른 것 같다. 12345678910111213141516171819202122232425262728293031323334#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); bool isPrime[1001]; memset(isPrime, true, sizeof(isPrime)); // 에라토스테네스의 체 이용하여 1000까지의 소수..

문제 링크 : https://boj.kr/2581 소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문에 소수 리스트를 미리 구해놓고 구하는 편이 빠른 연산 방법이..

문제링크 : https://boj.kr/2468 흰색으로 연결된 부분들의 갯수를 세는 문제다.갯수를 세는 것은 DFS로 풀면 되는데.. 문제는 1~100까지의 비 내리는 높이들을 하나 하나 다 계산해봐서 영역이 가장 많은 것을 구하는 것이다.어떻게 해야 효율적으로 구할 수 있을까 생각해봤는데.. 일단 풀었다.1~100까지의 횟수는 그리 많은 횟수가 아니라 시간 복잡도 상으로도 O(1)에 해당하기 때문에..그래서 1~100 까지의 모든 높이마다 각각 dfs를 그냥 돌렸는데 시간초과도 나지 않고 풀렸다. 이미 풀렸기 때문에 여기서 시간을 더 줄이는 효율적인 방법은 생각해보지 않았다.혹시나 해서 입력 받을때 최소 높이, 최대 높이를 추가로 체크해서 풀었는데 어짜피 시간은 똑같이 나왔다. 별로 의미가 없는듯 차..