0과 1의 쉼터

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

풀이 "백준 11726, 2×n 타일링" 문제와 비슷하다. 심지어 정답도.. 2x1 타일을 1, 1x2 타일을 2, 2x2 타일을 T라고 가정할 때 다음과 같이 나타낼 수 있다. N 타일 dp[1] 2 11 2, T 3 3 111 12,1T 21,2T 5 4 1111 112,11T 121,1T1 211,T11 22,TT 2T,T2 11 5 11111 1112,111T 1121,11T1 1211,1T11 2111,T111 122,1TT 212,T1T 221,TT1 12T,1T2 21T,T12 2T1,T21 21 6 " 43 7 " 85 8 " 171 N번째 방법의 수는 "2 * (N-2번째 방법의 수) + (N-1번째 방법의 수)" 와 같음을 알 수 있다. 소스코드 #include #define MOD 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(..

풀이 입력받은 시간을 오름차순으로 정렬 후, 기존의 대기시간(sum)과 i번째 사람이 인출하는데 걸리는 시간(arr[i])을 result에 누적 합으로 저장해주면 된다. 소스코드 #include #include int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); qsort(arr, N, sizeof(int), compare); int result = 0; for (int i = 0, sum = 0; i < N; result+=(sum+=arr[i++]))..

풀이 별을 아래의 그림처럼 노란색, 연두색, 하늘색으로 나누어 찍었다. if (abs(j) >= N-1 && abs(i) == N-1) putchar('*'); // 노란색 else putchar((abs(j)-abs(i) == N-1) || (abs(i)==abs(j)) ? '*' : 32); // 연두색 || 하늘색 마지막 별을 찍고 개행을 해야 한다는 점을 유의하자. 소스코드 #include #include int main(){ int N; scanf("%d", &N); for (int i = -N+1; i = N-1 && abs(i) == N-1) putchar('*'); else ..

풀이 별을 아래의 그림처럼 노란색, 연두색, 하늘색, 분홍색으로 나누어 찍었다. 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); } }..

소스코드 #include #include int main(){ int N; scanf("%d", &N); for (int i = -2*N+2; i < 2*N-1; i++){ for (int j = -2*N+2; j < 2*N-1; j++){ if (i%2==0 && abs(j)

풀이 알고리즘은 엄청 간단하다. N명의 이름을 입력받아서 정렬 후, M명의 이름을 입력받아 이진탐색으로 찾은 명단과 총 인원을 출력하면 된다. 하지만, 이를 C로 구현하는 것은 끔찍하다... 소스코드 #include #include #include #include using namespace std; int main(){ int N, M, i; scanf("%d %d", &N, &M); vector v1(N), v2; char name[21]; for (i = 0; i < N; i++){ scanf("%s", name); v1[i] = name; } sort(v1.begin(), v1.end()); for (i = 0; i < M; i++) { scanf("%s", name); if (binary_sea..

풀이 DFS는 방문 기록이 없는 정점만 탐색하면 된다. BFS는 방문한 정점을 visited뿐만 아니라 Queue에 순서대로 기록하고, front로 탐색의 기준점을, rear로 탐색의 중단점을 설정해주면 된다. 소스코드 #include #include int N, arr[1001][1001], visited[1001], queue[1001]; void dfs(int v){ visited[v] = 1; printf("%d ", v); for (int i = 1; i

풀이 입력받은 N을 이용해 정사각형을 분할하면서 전부다 1 또는 0일때까지 탐색을 하면 된다. 소스코드 #include int paper[128][128], w, b; void color(int x, int y, int n){ int cnt = 0; for (int i = x; i < x+n; i++) for (int j = y; j < y+n; j++) paper[i][j] && cnt++; if (cnt == n*n)b++; else if (!cnt) w++; else { color(x, y, n/2); color(x, y+n/2, n/2); color(x+n/2, y, n/2); color(x+n/2, y+n/2, n/2); } } int main(){ int N; scanf("%d", &N); f..