0과 1의 쉼터

풀이 (0, 0)부터 범위를 초과하지 않고, 이동할 수 있는 공간이고, 방문한적 없는 곳을 탐색하면 된다. 다음에 이동할 좌표 (tx, ty)를 구조체 q에 저장하고 front, rear을 이용해 탐색을 진행했다. 소스코드 #include #include bool visited[100][100]; int graph[100][100], d[100][100]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef struct{ int x, y; }Queue; void bfs(int N, int M){ d[0][0] = visited[0][0] = 1; Queue q[N*M]; q[0].x = q[0].y = 0; int x, y, front = 0, rear..

풀이 단순히 가장 큰 제곱수로 수를 구성하는 방법은 최소 제곱수의 개수의 만족이 성립하지 않는다. 때문에, 입력받은 n까지 모든 수에 대해 계산을 해봐야 한다. Square Free Integer같은 경우 이전의 수를 구성하는 제곱수의 개수 + 1을 만족하며 이러한 수의 밀집도는 리만 가설이 참이라는 전제하에 약 61%이다. ("백준 1557, 제곱 ㄴㄴ" 중 "Mobius function의 반환값의 개수 추측") 따라서 다음과 규칙을 기본으로 사용했다. for (int i = 1; i = 4 일 때는 Square Free Integer가 아닌 수들도 존재하며, 처음에 언급했듯이 가장 큰 제곱수의 구성이 최소 제곱수의 개수를 만족하지 않으므로, 구성 가능한 제곱수들 중 최소 제곱수의 개수를 찾아야 한다...

풀이 입력부터 애먹은 문제다. "[ , , ]"를 문자열로 입력받아서 해결해도 되지만, 정수만 입력받기 위해 ' [ ', ' ] '가 입력될 때는 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..

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

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

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