0과 1의 쉼터

풀이 "백준 2747, 피보나치 수"를 풀었던 방법으로 해결할 수 있다. 소스코드 #include const int MOD = 1e9 + 7; long long fibo(int n){ long long fiboNum[2] = {0, 1}; for (int i = 1 ; i < n; i++) fiboNum[(i+1)%2] = (fiboNum[i%2] + fiboNum[(i-1)%2]) %MOD; return fiboNum[n%2]; } int main(){ int n; scanf("%d", &n); printf("%lld", fibo(n)); } 출처 및 참고자료 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net..

풀이 "백준 15651, N과 M (3)"와 비슷하다. 1부터 N까지가 아닌 입력받은 수에 대해 모든 조합 가능한 수를 출력하면 된다. 소스코드 #include #include int N, M, visited[7], arr[7]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i < N; i++){ visited[depth] = arr[i]; if(depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ", visited[idx]); putchar(10); }else BT(depth + 1); } } i..

풀이 "백준 15664, N과 M (10)"에서 사용한 코드로 해결이 된다. 소스코드 #include #include #include bool check[8]; int N, M, arr[8], visited[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth, int start){ for (int i = start, temp = 0; i < N; i++) if (!check[i] && temp != arr[i]){ temp = visited[depth] = arr[i]; check[i] = true; if (depth + 1 == M){ for (int idx = 0; idx < M; i..

풀이 모든 조합 가능한 수를 출력하면 된다. 소스코드 #include int N, M, visited[7]; void BT(int depth){ for (int i = 1; i

풀이 의상의 종류별로 개수를 세고, 의상을 입어볼 수 있는 모든 경우에서, 모든 의상을 다 입은 경우만 빼면 된다. 소스코드 #include #include #include using namespace std; int main(){ int T, n; cin >> T; while (T--){ cin >> n; map info; map::iterator iter; string name, kinds; while (n--){ cin >> name >> kinds; if (info[kinds]) info[kinds]++; else info[kinds] = 1; } int result = 1; for (iter = info.begin(); iter != info.end(); iter++) result *= (ite..

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

풀이 "백준 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이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 ..