컴공과고씨

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 간단 정리 정말 간단하다 a,b,c가 주어짐. a^b을 구하는 문제임. 단 a^b값이 너무 클 수 있으니 c로 나눈 나머지를 구하면됨. 문제 해결 방법 일단 나머지 정리를 알아야함. 나머지 정리는 그냥 간단하게 그냥 ((a%c) * (b%c) %c) 하고 (a*b)%c 같다. 즉, 이런 문제가 나오면 그냥 나머지 구하고 곱해주고 나머지 구해주면 된다. 제한 시간이 2초이기 때문에 1초에 3~5억번 연산을 한다고 했을 때 문제의 주어진 수가 최대 21억이기 ..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 유형을 보고 분할정복을 떠올려 풀어준 문제이다. 각 변을 3씩 나누면서 보면 탐색하는 문제이다. 보면 처음에 9로 시작한다. 모든 원소가 같지 않다면 n/3으로 나누고 각 분면의 시작 좌표로 이동해주어야한다. ​이런식의 좌표가 나온다. y가 행 x는 열. 단계별 풀이 1. 입력을 받아주고 papper 재귀함수로 들어간다. 2. bool 변수 선언 후 각 분면에 있는 원소들을 탐색해..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제를 보고 분할 정복을 사용해서 풀 수 있겠다는 생각이 들었다. 일단 분할 정복 같은 경우는 큰 문제를 작은 문제로 나눠서 푸는 방법이다. 지금 같은 경우 큰 정사각형에서 크기가 4인 정사각형까지 쪼개서 풀어주면 쉽다. 큰 정사각형은 4분할 해서 4개의 정사각형을 만들 수 있다. 그리고 조건문을 사용해서 4분면 중 위 순서대로 검사를 하여 구하고자하는 위치가 어디에 속해 있는지 확인해주..