0과 1의 쉼터

풀이 비트 연산자를 사용해 풀이할 수 있다. 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이다. 소스코드 #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

소스코드 #include int main() { int arr[5], sum = 0; for (int i = 0; i < 5; i++) { scanf("%d", &arr[i]); arr[i] < 40 && (arr[i] = 40); sum += arr[i]; } printf("%d\n", sum / 5); } 출처 10039번: 평균 점수 입력은 총 5줄로 이루어져 있고, 원섭이의 점수, 세희의 점수, 상근이의 점수, 숭이의 점수, 강수의 점수가 순서대로 주어진다. 점수는 모두 0점 이상, 100점 이하인 5의 배수이다. 따라서, 평균 점 www.acmicpc.net

소스코드 #include int main() { int A, B; scanf("%d %d", &A, &B); printf("%d", A + B); } 출처 2558번: A+B - 2 첫째 줄에 A, 둘째 줄에 B가 주어진다. (0 < A, B < 10) www.acmicpc.net

풀이 10의 10000승이므로 개행문자 까지 포함해 A, B에는 최대 10002개의 문자가, 두 수의 합을 저장할 배열은 최대 10003개의 문자를 담을 수 있어야 한다. 문자열로 입력받았기 때문에 자리올림을 위해 문자열을 뒤집어 주어야 한다. 백준 채점 환경에서는 strrev()를 사용할 수 없어 직접 구현했다. 두 문자열의 문자에 해당하는 아스키코드값을 이용해 덧셈을 해주며, 자리올림이 발생하면 다음 계산 때 적용한다. 소스코드 #include #include void str_rev(char *str, int len){ for (int i = 0; i < len/2; i++){ str[i] = str[i] ^ str[len-i-1]; str[len-i-1] = str[len-i-1] ^ str[i];..

풀이 "백준 2747, 피보나치 수"와 동일한 방법으로 풀이할 수 있다. 소스코드 #include int fibo(int n){ int fiboNum[2] = {0, 1}; for (int i = 1 ; i < n; i++) fiboNum[(i+1)%2] = fiboNum[i%2] + fiboNum[(i-1)%2]; return fiboNum[n%2]; } int main(){ int n; scanf("%d", &n); printf("%d", fibo(n)); } 출처 및 참고자료 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1..

풀이 "백준 2747, 피보나치 수"에서 사용한 Dynamic Programming 풀이방식을 재사용해 시간초과는 발생하지 않지만, 수가 너무 커서 long long 형을 사용해주어야 한다. 소스코드 #include long long fibo(int n){ long long fiboNum[2] = {0, 1}; for (int i = 1 ; i < n; i++) fiboNum[(i+1)%2] = fiboNum[i%2] + fiboNum[(i-1)%2]; return fiboNum[n%2]; } int main(){ int n; scanf("%d", &n); printf("%lld", fibo(n)); } 출처 및 참고자료 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수..