0과 1의 쉼터

풀이 구조체 배열의 index와 문자열을 이용해 숫자를 입력받을 떄는 별도의 탐색없이 출력이 가능하지만, 문자열 검색시에는 탐색을 필요로 하고, 이 과정에서 시간 초과가 발생해 map을 사용해 풀이했다. 소스코드 #include #include #include #include using namespace std; map name; map num; int main(){ int N, M; scanf("%d %d", &N, &M); char temp[21]; for (int i = 0; i < N; i++){ scanf("%s", temp); name[temp] = i; num[i] = temp; } for (int i = 0; i < M; i++){ scanf("%s", temp); if (temp[0]

풀이 Pisano Period를 이용해 풀이했다. 위의 내용 처럼 피보나치 수를 특정 수(n)으로 나눌 때 나머지들은 일정 주기마다 반복되는 것을 알 수 있다. 이러한 주기를 Pisano Period라고 부른다. Pisano Period는 다음과 같이 이용된다. n번째 피보나치 수를 MOD로 나눈 나머지는, N % (Pisano Period) 번째 피보나치 수를 MOD로 나눈 나머지와 같다. Pisano Period번 째의 피보나치 수가 필요하며, 이번 문제에 필요한 Pisano Period를 구하는 방법은 다음과 같다. MOD가 10의 6승이므로 Pisano Period는 1500000 = 15 * 10 ^(5) 이다. 소스코드 #include #define MOD 1000000 #define P 15..

풀이 정답은 2의 K제곱들의 합이다. "백준 13731, A" 문제에서 2의 제곱을 구하는 방식을 이용해 풀이했다. 2의 K제곱(D)들의 합(sum_D)을 차수와 계수의 곱에 곱해주는 것을 반복하면 된다. 소스코드 #include #define MOD 1000000007 int main() { int N; scanf("%d", &N); long long result = 0, C, K; for (int i = 0; i < N; i++) { scanf("%d %d", &C, &K); long long DC = (C*K)%MOD, sum_D = 1, D = 2; K--; while (K) { if (K & 1) sum_D = sum_D*D %MOD; D = D*D %MOD; K /= 2; } result = ..

소스코드 #include int main(){ int N, n1, n2, result = 0; scanf("%d", &N); for (int i = 0; i < N; i++){ scanf("%d %d", &n1, &n2); result += n1*n2; } printf("%d", result); } 출처 14730번: 謎紛芥索紀 (Small) 성민이는 이번 학기에 미적분학 과목을 수강하고 있다. 다항함수의 미분 단원 과제를 하던 도중 미분을 하기가 귀찮아진 성민이는 미분하려는 함수 f(x)가 주어지면, 미분 된 함수 f’(x)를 자동 www.acmicpc.net

풀이 비트 연산자를 사용해 풀이할 수 있다. X의 이진수를 right shift 해주면서, A를 한 번씩 제곱해주다가, X의 이진수의 가장 끝(맨 오른쪽) 숫자가 1일 때, result에 곱해주는 방식으로 풀이했다. A = 2, X = 6일 때 A X X & 1 result 2 110 false 1 4 11 true 4 16 1 true 64 0 소스코드 #include #define MOD 1000000007 int main() { unsigned long long A, X, result = 1; scanf("%llu %llu", &A, &X); A %= MOD; while (X > 0){ if (X & 1) result = (result*A) % MOD; X >>= 1; A = (A*A) % MOD;..

풀이 분할 정복을 이용한 거듭제곱 알고리즘의 기초적인 방법으로 풀이했다. 입력된 수는 int형으로 충분히 담아낼 수 있지만, 두 수의 곱은 이를 벗어나기 때문에, long long형으로 담아주어야 한다. Test Case에 주어지는 C의 값은 결과를 int형으로 출력할 수 있게 주어지는 듯 했다. 착한 문제지 쉬운 문제는 아니다. 홀수의 경우에는 A를 한번 더 곱해서 맞춰주어야 하므로 (B%2 ? A : 1) 으로 해결했다. 소스코드 #include long long mul(int A, int B, int C) { if (B > 1) { long long temp = mul(A, B/2, C); return ((temp*temp)%C * (B%2 ? A : 1)) % C; } else return A; ..

풀이 사분면을 탐색해 방문횟수를 반환하는 방식보다는, 전체 허용 범위내 조건 충족시 출력을 하는 방식으로 풀이했다. 허용 범위가 아니라면, 다른 사분면에 있으므로 n*n을 누적해준다. 소스코드 #include int r, c, cnt; void Z(int row, int col, int n){ if (row == r && col == c){ printf("%d\n", cnt); return; } if (r >= row && c >= col && r < row + n && c < col + n) { Z(row, col, n/2); Z(row, col + n/2, n/2); Z(row + n/2, col, n/2); Z(row + n/2, col + n/2, n/2); } else cnt += n*n; } ..

풀이 약수가 모두 주어지므로 가장 작은 약수와 가장 큰 약수의 곱이 N이다. 소스코드 #include int main(){ int N, val, max, min; scanf("%d", &N); for (int i = 0; i max && (max = val); val < min && (min = val); } printf("%d", max*min); } 출처 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, ..

풀이 분 단위로 시간을 입력받아 24시로 표현하면 된다. 소스코드 #include int main(){ int H, M, time; scanf("%d %d %d", &H, &M, &time); printf("%d %d", (H+((M+time)/60))%24, (M+time)%60); } 출처 2525번: 오븐 시계 첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.) www.acmicpc.net

소스코드 #include int main() { int arr[5], price = 2000; for (int i = 0; i < 5; i++){ scanf("%d", &arr[i]); if (i < 3 && arr[i] < price) price = arr[i]; } printf("%d\n",price + (arr[3] < arr[4] ? arr[3] : arr[4]) - 50); } 출처 5543번: 상근날드 입력은 총 다섯 줄이다. 첫째 줄에는 상덕버거, 둘째 줄에는 중덕버거, 셋째 줄에는 하덕버거의 가격이 주어진다. 넷째 줄에는 콜라의 가격, 다섯째 줄에는 사이다의 가격이 주어진다. 모든 가 www.acmicpc.net