일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 너비 우선 탐색
- 수학
- 브론즈
- 브론즈 III
- solved.ac class
- PS
- 한국정보올림피아드
- 백트래킹
- 그래프 탐색
- 실버
- 브론즈 II
- 문자열
- 그래프 이론
- 사칙연산
- Class 1
- 골드
- Class 4
- 브루트포스 알고리즘
- 실버 V
- class 5
- Class 2
- 정수론
- practice
- Easy
- 구현
- greedy
- Class 3
- 정렬
- 실버 III
- 다이나믹 프로그래밍
- Today
- Total
목록실버 III (33)
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..
풀이 N >= 4 일때 다음과 같이 풀이할 수 있다. 현재 계단 + N-1번째 계단 + N-3번째 계단까지 최댓값이나, 현재 계단 + N-2번째 계단까지 최댓값 중 큰 값이 N번째 계단까지의 최댓값이다. 소스코드 #include #define max(a,b) a > b ? a : b int main(){ int N; scanf("%d", &N); int arr[N], dp[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); dp[0] = arr[0]; dp[1] = max(arr[0], arr[0]+arr[1]); dp[2] = max(arr[0]+arr[2], arr[1]+arr[2]); for (int i = 3; i < N; i++) dp[i] = max..
풀이 "백준 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..