0과 1의 쉼터

풀이 "백준 15664, N과 M (10)"에서 기존에 i번째 요소를 사용했는지를 확인하기 위해 사용한 check를 빼면 해결할 수 있다. 소스코드 #include #include 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 (temp != arr[i]){ temp = visited[depth] = arr[i]; if (depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ",..

풀이 "백준 15663, N과 M (9)"에서 기존에 i번째 요소를 사용했는지를 확인하기 위해 사용한 check를 빼면 해결할 수 있다. 소스코드 #include #include int N, M, arr[7], visited[7]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0, temp = 0; i < N; i++) if (temp != arr[i]){ temp = visited[depth] = arr[i]; if (depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ", visited[idx]); ..

풀이 "백준 15663, N과 M (9)"를 참고해서 풀이했다. 요소의 중복은 temp와 check로 관리가 가능하니, 이전에 사용했던 요소의 인덱스를 탐색 시작점으로 이용하면 된다. 소스코드 #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번째 요소를 사용했는지, 기존에 사용한 숫자와 현재 사용하고자 하는 숫자가 다른지 확인하는 방식으로 풀이했다. 소스코드 #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){ for (int i = 0, temp = 0; i < N; i++) if (!check[i] && temp != arr[i]){ temp = visited[depth..

풀이 "백준 9095, 1, 2, 3 더하기"의 확장 문제이다. 1e6 까지 미리 구해놓자. 소스코드 #include const int MOD = 1e9+9; int dp[1000001] = {1, 2, 4}; int main(){ for (int i = 3; i < 1000001; i++) dp[i] = ((dp[i-1]+dp[i-2])%MOD +dp[i-3]) %MOD; int N, T; for (scanf("%d", &T); T--;){ scanf("%d", &N); printf("%d\n", dp[N-1]); } } 출처 및 참고자료 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. ..

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

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

풀이 가치가 가장 큰 동전부터 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..

풀이 입력받은 좌표들을 오름차순으로 정렬하고, 중복을 제거했을 때, 각 요소들이 몇 번째인지 출력하는 문제다. 입력받은 수들을 두 벡터에 저장하고, v2는 오름차순으로 정렬 후, 중복을 제거했다. 중복된 수가 제거된 v2에서 lower_bound()를 사용하면, 원하는 결과를 얻을 수 있다. 소스코드 #include #include #include using namespace std; int main(){ int N, temp; scanf("%d", &N); vector v1(N), v2(N); for (int i = 0; i < N; i++){ scanf("%d", &temp); v1[i] = v2[i] = temp; } sort(v2.begin(), v2.end()); v2.resize(unique(..

풀이 별을 아래의 그림처럼 노란색, 연두색, 하늘색, 분홍색으로 나누어 찍었다. void mark_star(int p, int N){ if (N == 1) arr[p][p] = arr[p+1][p] = arr[p+2][p] = '*'; // 노란색 else { int row = 4*N-1, col = row-2; for (int i = p; i < p+col; i++) arr[p][i] = arr[p+row-1][i] = '*'; // 연두색 for (int i = p+2; i < p+row-1; i++) arr[i][p] = arr[i][p+col-1] = '*'; // 하늘색 arr[p+1][p] = arr[p+2][p+col-2] = '*'; // 분홍색 mark_star(p+2, N-1); } }..