Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 동적계획법
  • UC++
  • C++
  • 스택
  • 백트래킹
  • 정수론
  • 브루트포스
  • 구현
  • 조합론
  • LCA
  • 백준
  • SCC
  • 그래프
  • 투포인터
  • 기하
  • 트라이
  • 유니온 파인드
  • 위상 정렬
  • KMP
  • 정렬
  • 분할정복
  • 트리
  • 세그먼트 트리
  • 최소 스패닝 트리
  • 수학
  • 누적합
  • 우선순위큐
  • 큐
  • 이분탐색
  • 문자열

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 1629번 문제
공부 및 정리/백준 코드

[C++]백준 - 1629번 문제

2021. 8. 5. 18:08

1629번: 곱셈 (acmicpc.net)

 

1629번: 곱셈

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

www.acmicpc.net

 

1629번 : 곱셈


자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력


첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

 

출력


첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

 


 

생각해 볼 점


우선 A, B, C가 모두 int의 최댓값 -1로 주어지긴 했지만, 범위가 넘어갈 우려가 있으니 long long을 씁니다.

 

분할 정복법을 사용하여, 최대한 적은 계산 횟수로 제곱수를 구해낼 것입니다.

 

방법은 다음과 같습니다.

 

 

A^B일 때, B가 짝수면

 

A ^ (B / 2)의 제곱을 구합니다.

 

B가 홀수면, A * A^(B - 1)을 구합니다.

 

재귀함수로 이를 해결한다고 생각해봅시다.

 

함수 Solution(i)는 A의 i제곱의 값을 반환합니다.

 

Solution(i) = (Solution(i / 2))^2   

혹은,

Solution(i) = Solution(i -1) * A

 

가 될 것입니다. 이렇게 풀면 우리는 많은 반복을 하지 않고도 빠르게 제곱수를 구할 수 있습니다.

 

문제에 있는 C로 나눈 나머지의 경우는 나머지 정리를 알고 있어야 합니다.

 

(A * B)의 나머지 = A의 나머지 * B의 나머지 입니다.

 

따라서, 곱셈 연산마다 C로 나눈 나머지를 반환해주면 됩니다.

 

코드


 

#include <iostream>
using namespace std;

long long N, D;

//분할 정복
long long solution(long long K)
{
    if(K == 1) return N % D;
    if(K % 2 == 0)
    {
        long long result = solution(K / 2);
        return (result * result) % D;
    }
    else
    {
        return (solution(K - 1) * N) % D;
    }
}

int main() 
{
	int K;
	cin >> N >> K >> D;
	
	cout << solution(K);
	
	return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 10942번 문제  (0) 2021.08.08
[C++]백준 - 1520번 문제  (0) 2021.08.05
[C++]백준 - 12865번 문제  (0) 2021.08.05
[C++]백준 - 1912번 문제  (0) 2021.08.05
[C++]백준 - 11049번 문제  (0) 2021.08.01
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 10942번 문제
    • [C++]백준 - 1520번 문제
    • [C++]백준 - 12865번 문제
    • [C++]백준 - 1912번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바