기록보관소

마인크래프트 문제는 지형을 평탄화할 수 있는 모든 경우를 고려하여 계산하는 문제이다. 평탄화된 지형의 최소 높이는 0, 최대 높이는 지면의 블록 개수와 인벤토리에 있는 블록 개수를 면적으로 나눈 값이다. 이 두 값 사이의 값을 높이로 가지기 위해 블록을 부수거나 쌓아야 하는 데 이때 가장 시간이 적게 걸리는 높이를 찾으면 된다. 작성한 코드는 다음과 같다. #include int N, M, B; int land[520][520]; int sum = 0; int time; int min=987654321; int height; int main(void) { scanf("%d %d %d", &N, &M, &B); for (int i = 0; i < N; i++) { for (int j = 0; j < M; ..

팰린드롬수 문제는 문자열을 다루는 문제이다. 문자열을 대칭적으로 확인하여 같지 않으면 no를 출력하고, 전부 같으면 yes를 출력하도록 함수를 작성하면 된다. 작성한 코드는 다음과 같다. #include #include char temp[10]; int func() { int length = strlen(temp); if (length == 1) { if(temp[0] == '0') return -1; else { return 1; } } else { for (int i = 0;i

조합 0의 개수 문제는 소인수 분해시 2와 5의 개수를 활용하는 문제입니다. 팩토리얼 값을 소인수 분해했을 때 5의 개수를 구하는 방법은 팩토리얼에서 처음의 항을 5로 나눈 수 + 25로 나눈 수 + 125로 나눈 수 + .... 식과 같다. 이런 방식으로 2와 5의 개수를 찾고 그 중 가장 작은 값이 0의 개수가 된다. 작성한 코드는 다음과 같다. #include long long int n, m; long long int five, two; long long int d; int main(void) { scanf("%lld %lld", &n, &m); d = 5; while (1) { if ((n< d)) break; five += (n / d); d *= 5; } d = 2; while (1) { i..

팩토리얼 0의 개수 문제는 팩토리얼 값을 소인수분해를 하였을 때 2와 5의 지수 중 최소값을 활용하는 문제입니다. 0의 개수는 2와 5의 지수 중 최소의 개수와 동일하다는 사실을 이용하면 됩니다. 작성한 코드는 다음과 같습니다. #include int N; int result = 1; int cnt = 0; int two, five; int temp; int main(void) { scanf("%d", &N); for (int i = 1; i five) printf("%d\n", five); else printf("\n", two); } } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/1676

패션왕 신해빈 문제는 경우의 수를 이용한 문제입니다. (같은 종류의 개수 + 1) 항들의 곱에 -1을 한 값이 옷을 입을 수 있는 경우의 수가 됩니다. 작성한 코드는 다음과 같습니다. #include #include int T; int n; char temp[100]; char clothes[300][100]; char cnt[300]; int limit; int result = 1; int k; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d", &n); result = 1; limit = 0; for (int j = 0; j < 2*n; j++) { scanf("%s", temp); if (j % 2 == 1) { f..

다리 놓기 문제는 조합을 사용하는 문제입니다. mCn의 공식을 활용하여 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include int T; int N, M; int result = 1; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { result = 1; scanf("%d %d", &N, &M); for (int j = 0; j < N; j++) { result = result * (M--) / (j + 1); } printf("%d\n", result); } } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/1010

이항 계수 2문제는 이항 계수 점화식뿐만 아니라 다이나믹 프로그래밍 기법을 활용하는 문제입니다. (n, k) = (n-1, k-1) + (n-1, k)라는 사실과 배열을 활용하여 (n, k)를 미리 계산한 후 출력함으로써 풀 수 있습니다. 다이나믹 프로그래밍을 할 때 기교를 발휘하면 배열의 크기는 1차원 배열 [1001]까지 줄일 수 있습니다. 작성한 코드에서는 2차원 배열 [2][1001]로 작성하였습니다. #include //NCK int N, K; int result[2][1001]; int i=1; int main(void) { scanf("%d %d", &N, &K); result[0][0] = 1; result[1][0] = 1; while (1) { for (int j = 1; j < 100..

링 문제는 원주의 비율과 최대공약수를 활용하는 문제입니다. 원주가 반지름에 비례한다는 사실을 이용하여 회전수를 구하고 최대공약수를 이용하여 기약분수 형태로 출력함으로써 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include //기약분수는 최대공약수로 생성 int N; int temp, temp1, temp2; int gcd(int a, int b) { int temp; if (a < b) { temp = b; b = a; a = temp; } while (a % b != 0) { temp = b; b = a % b; a = temp; } return b; } int main(void) { scanf("%d", &N); scanf("%d", &temp1); for (int i = 0;..