0과 1의 쉼터

풀이 "백준 15652, N과 M (4)"를 참고해 풀이했다. 기존에는 1부터 입력받은 N까지의 수들 중에서 수열을 생성해야 했다. 이번에는 N개의 수를 이용해 수열을 생성하면 된다. 소스코드 #include #include int arr[8], N, M, num[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i num[i]) break; if (j == depth) arr[depth]..

풀이 "백준 15649, N과 M (1)"을 참고해서 풀이했다. 기존에는 1부터 입력받은 N까지의 수들 중에서 수열을 생성해야 했다. 이번에는 N개의 수를 이용해 수열을 생성하면 된다. 소스코드 #include #include int arr[8], N, M, num[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i < N; i++){ if (!depth) arr[0] = num[i]; else{ int j; for (j = 0; j < depth; j++) if (arr[j] == num[i]) break; if (j == depth) arr[dept..

풀이 "백준 15650, N과 M (2)"를 참고해서 풀이했다. 기존의 코드에 같은 수를 여러번 고를 수 있도록 수정만 하면 된다. for (j = 0; j i) break; // arr[j]에 담긴 수보다 작은 경우에만 저장하지 않는다. 소스코드 #include int arr[8], N, M; void BT(int depth){ for (int i = 1; i i) break; if (j == depth) arr[depth] = i; else continue; } if (depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ", arr[idx]); putchar(10); }else BT(depth ..

풀이 F(1) = 1 = F(0) + F(-1), F(-1) = 1 F(0) = 0 = F(-1) + F(-2), F(-2) = -1 F(-1) = 1 = F(-2) + F(-3), F(-3) = 2 F(-2) = -1 = F(-3) + F(-4), F(-4) = -3 F(-3) = 2 = F(-4) + F(-5), F(-5) = 5 n이 음수이고, 짝수일때만, F(n)이 -1이다. 소스코드 #include int main(){ int n, op = 1; long long dp[2] = {0, 1}; scanf("%d", &n); if (n = 2){ for (int i = 1; i..

풀이 "백준 15649, N과 M (1)"를 참고해서 풀이했다. 이전 문제에서는 아래 코드와 같이 중복되는 수열을 거르기 위한 조건을 사용했다. for (j = 0; j = i) break; // arr[j]에 담긴 수보다 작거나 같을 경우 저장하지 않는다. 소스코드 #include int arr[8], N, M; void BT(int depth){ for (int..

풀이 P(N >= 5)는 P(N-4) + P(N-1)과 같다. 생각보다 큰 숫자가 나온다 long long형으로 값을 저장해주자. 소스코드 #include int main(){ int T, N; long long dp[100] = {1, 1, 1, 2, 2}; for (int i = 5; i < 100; i++) dp[i] = dp[i-5] + dp[i-1]; scanf("%d", &T); while (T--){ scanf("%d", &N); printf("%lld\n", dp[N-1]); } } 출처 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 ..

풀이 9등분을 하고, n/3만큼 좌표를 (x, y) 증가시켜 Divide and Conquer 하면 된다. N만큼의 종이가 모두 같을 때, 탐색을 중단해야 하므로 중단 조건을 함수로 만들어 풀이했다. 소스코드 #include int paper[2187][2187], I[3]; int all_same_paper(int x, int y, int n){ int temp = paper[x][y]; for (int i = x; i < x+n; i++) for (int j = y; j < y+n; j++) if (paper[i][j] != temp) return 0; return 1; } void division(int x, int y, int n){ if (all_same_paper(x, y, n)) I[pape..

소스코드 #include int N; const char *str[7] = { "\"재귀함수가 뭔가요?\"", "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.", "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.", "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"", "\"재귀함수가 뭔가요?\"", "\"재귀함수는 자기 자신을 호출하는 함수라네\"", "라고 답변하였지." }; void message(int n){ for (int i = 0; i < 4; i++){ for (int j = 1; j < n; j++) printf("____"); puts(str[i]); } if (n..

풀이 0의 개수는 2와 5의 곱의 쌍을 통해 알 수 있다. (2*5 = 10, 15 * 2 = 30) 하지만 팩토리얼이기 때문에 2의 배수는 무수히 많으므로, 5의 제곱수의 개수만 알아내면 된다. N은 최대 500이하 이므로, 125, 25, 5로 나누어 떨어지는 경우만 해당한다. 소스코드 #include int main(){ int N, cnt = 0; scanf("%d",&N); for(int i = 1 ; i

풀이 가치가 n인 동전으로 k를 만드는 경우의 수는 k-n을 만드는 경우의 수와 같다. (단, k-n = 0의 경우의 수는 1로 설정) ex) n = 2, k 1 2 3 4 5 6 7 경우의 수 0 1 0 1 0 1 0 가치가 n1, n2인 동전으로 k를 만드는 경우의 수는 "k-n을 만드는 경우의 수 + n1으로 k를 만드는 경우의 수"와 같다. ex) n1 = 1, n2 = 2 k 1 2 3 4 5 6 7 8 9 10 n1 1 1 1 1 1 1 1 1 1 1 n2 2 2 3 3 4 4 5 5 6 이를 코드로 표현하면 다음과 같다. for (int i = 0; i < n; i++) for (int j = coin[i]; j