[백준] 1629 - 곱셈
문제링크 https://www.acmicpc.net/problem/1629 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 조건 시간 제한 : 0.5s 메모리 제한 : 128MB 해설 굳이 A^B의 전체 수를 구한 다음 C로 나누어 나머지를 구하지 말고, 계속해서 나머지를 이용해 그 다음 나머지를 구해나가면 작은 메모리 안에서 해결이 가능하다. A B C 가 10 11 12라고 하면 result는 A^B %..
문제링크https://www.acmicpc.net/problem/2170조건시간 제한 : 1s메모리 제한 : 192MB문제매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.입력첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,..
문제링크https://www.acmicpc.net/problem/1934문제두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)출력첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.조건시간 제한 : 1s메모리 제한 : 128M..
문제링크https://www.acmicpc.net/problem/1676문제N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)출력첫째 줄에 구한 0의 개수를 출력한다.조건시간 제한 : 2s메모리 제한 : 128MB해설1부터 N까지의 수들을 곱했을 때, 그 수에 10이 몇 번 곱해질 수 있는 지를 묻는 문제이다. 10을 만들기 위해 2와 5가 사용되고, 2는 짝수에 모두 포함되어 있기 때문에, 5의 개수만 세어주면 된다. 소인수분해 했을 때 5가 포함되는 값들은 5의 배수이고, 25의 배수는 5가 2개, 125의 배수는 5가 3개 포함된다. 풀이5의 배수, 25의 배수, 125의 배수를 헤아리는 방법은 해당..
문제링크https://www.acmicpc.net/problem/1780문제N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 ..
문제링크https://www.acmicpc.net/problem/1976조건시간 제한 : 2s메모리 제한 : 128MB문제동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 ..
문제링크https://www.acmicpc.net/problem/2630문제아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로..
문제링크https://www.acmicpc.net/problem/1717조건시간 제한 : 2s메모리 제한 : 128MB문제초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.입력첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산..
문제링크https://www.acmicpc.net/problem/2004문제nCm 의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.입력첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.출력첫째 줄에 nCm 의 끝자리 0의 개수를 출력한다.조건시간 제한 : 2s메모리 제한 : 128MB해설nCm의 값을 나타내는 곱의 형태에서 2와 5의 개수를 각 카운트 하여 10을 얼마나 만들 수 있는지를 찾는다. 풀이N!에 5의 개수를 N5, M!의 5의 개수를 M5, N-M의 5의 개수를 NminusM5라고 하고, 2에 대해서도 N2, M2, NminusM2라고 선언하자.N의 5의 배수를 저장하는 과정에서, N을 5로 나눈 몫을 이용하면 5의 배수에서 5를 하나씩 뽑아낼 수 있다..
문제링크https://www.acmicpc.net/problem/11050문제이하 이항 계수를 아래와 같이 표기한다.(N,K)→(NK)(N, K) → \binom{N}{K}(N,K)→(KN)자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N)출력(N, K)를 출력한다.조건시간 제한 : 1s메모리 제한 : 256MB해설입력되는 값의 크기가 그렇게 크지 않으므로, 이항 계수를 구하는 수식적인 방법을 그대로 이용하여 값을 구해준다.N ~ N-K+1 까지 곱한 값에 1 ~ K 까지 곱한 값을 나눈 결과를 출력한다. 풀이해설에 적힌 방법대로 N 부터 N-K+1 까지를 result에 차례대로 곱하고,..