728x90 C++15 [C++][백준] 11819 The Shortest does not Mean the Simplest 1629번 곱셈 문제와 동일하지만 수 범위가 더 큰 문제이다.문제자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 자세한 설명은 여기 있으니 관심있다면 한번 보도록 하자.https://cromcode.tistory.com/15 코드를 살펴보자#includeusing namespace std;using ull = unsigned long long;__int128_t ipow(ull a, ull b, ull c){ .. 2024. 7. 4. [C++][백준] 1629 곱셈 이번 문제는 빠른 거듭제곱을 활용하면 쉽고 빠르게 풀 수 있다.빠른 거듭제곱이 뭘까?어떤 숫자 x를 n번 거듭제곱 한다고 하면 x를 n번 곱하는 것이 일반적인 계산법이다. 예를들어 2의 31제곱을 구해야 한다고 하자. 그렇다면 계산 과정은 아래와 같을 것이다.2x2x2x2x2x2x2x2x2x2x....x2x2x2x2x2x2x2x2x2x2x2x2x2x2(31번 곱했다고 치자.) 이 방법의 경우는 시간복잡도가 O(n)이다. 만약 n이 아주 큰 수라면 계산하는 시간이 오래 걸리게 될 것이다. 더 빨리 구하는 방법은 무엇일까? 생각을 약간 틀어서 지수인 31을 이진수로 생각해보자. 31 => 11111(2)이다. 211111(2)을 계산한다고 생각하면24 x 23 x 22 x 21 x 20 만 계산하면 된다. .. 2024. 7. 3. [C++][백준] 17466 N! mod P(1) 이번 문제는 간단한 팩토리얼 문제이다.문제양의 정수 N과, N보다 큰 소수 P가 주어질 때, N!을 P로 나눈 나머지를 구하여라. 입력첫째 줄에 N과 P가 공백으로 구분되어 주어진다. 출력N!을 P로 나눈 나머지를 구하여라. 제한1 ≤ N P는 소수 코드를 살펴보자#includeusing namespace std;int main(){ long long n,p,r=1; cin >> n >> p; while(n) { if (n == 0) break; r = r*n%p; n--; } cout 사실 N과 P의 범위가 108이하이기 때문에 int범위로 선언해도 되지만 최종 값을 저장할 r의 값은 오버플로우가 날 경우가 생길 .. 2024. 7. 3. [C++][백준] 4307 개미 이번 문제는 간단한 구현 문제이다.문제는 어려워 보이지만 약간 생각을 다르게 한다면 쉬운 문제가 된다.문제개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개.. 2024. 7. 1. [C++][백준] 1990 소수인팰린드롬 이번 문제는 소수판정과 팰린드롬 판정을 하는 문제이다.문제151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다.팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오. 입력입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a 출력첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다. 아이디어 소수를 판정하기 위해서는 에라토스테네스의 체 방법을 사용하는 것이 편하다.에라토스테네스의.. 2024. 7. 1. [C++][백준] 1074 Z 이 문제는 재귀를 사용하는 문제이다.문제한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 22 × 22 크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다.입력첫째 줄에 정수 N, r, c가 주어진다.출력r행 c열을 몇 번째로 방문했는지 출력한다. 처음에는 2^15인 2차원 배열을 만든 다음 재귀 함수를 돌려 순차적으로 채워나가는 것을 생각해봤다.그렇지만 시간제한이 0.5초.. 2024. 7. 1. 이전 1 2 3 다음 728x90 반응형
