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 ..

풀이 입력부터 애먹은 문제다. "[ , , ]"를 문자열로 입력받아서 해결해도 되지만, 정수만 입력받기 위해 ' [ ', ' ] '가 입력될 때는 getchar()로 buffer를 비워 다음 입력에 영향이 안가도록 했다. getchar(); for (int i = 0; i < n; i++) scanf("%d,", &x[i]); getchar(); error가 뜨는 경우는 다음과 같다. n = 0일 때 n = 0이 아니지만, p에 입력받은 D의 개수보다 n이 작을 때 2번째 조건을 확인하기 위해 n을 감소시켜 반복문이 끝나기 전에 1번째 조건으로 유도하는 방법으로 구현했다. for (int i = 0; p[i] != '\0'; i++){ if (p[i] == 'R') reverse = reverse ? 0..

풀이 "백준 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..

풀이 Dynamic Programming의 Memorization 방식으로 풀이했다. (S~E) 구간이 팰린드롬인지 알기 위해서는 (S+1 ~ E-1), (S+2 ~ E-2), ... (X, X+1) or (X, X)구간의 수들이 팰린드롬인지 알아내는 과정을 반복해야한다. 길이가 3이상일 때, 요소가 홀수개인 팰린드롬은 최종적으로 길이가 1인 팰린드롬의 여부에 따라, 요소가 짝수개인 팰린드롬은 최종적으로 길이가 2인 팰린드롬의 여부에 따라 결정되기 때문에 다음과 같이 나누었다. 입력을 받을 때 길이가 1, 2인 펠림드롬을 확인하고, for (int i = 1; i 1 && arr[i] == arr[i-1]) dp[i-1][i] = 1; } 입력이 끝난 후 길이가 3 이상인 팰린드롬을 구했다. for (i..

풀이 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

풀이 가치가 가장 큰 동전부터 K이하일 때 하나씩 빼주고 횟수를 세주면 된다. 소스코드 #include int main(){ int N, K; scanf("%d %d", &N, &K); int coin[N]; for (int i = 0; i < N; i++) scanf("%d", &coin[i]); int cnt = 0, idx = N-1; while (K) if (K < coin[idx]) idx--; else { K -= coin[idx]; cnt++; } printf("%d", cnt); } 출처 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1..