분류 전체보기 54

백준 BOJ 10830 행렬제곱

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해설 단순히 행렬 제곱을 구하는 문제다. B가 크므로 행렬의 제곱을 분할 정복하도록 한다. 주의할 점은 아래 두 가지다. 1. B가 매우 큰 수 이므로 long long으로 받아야 한다는 것 2. 각 원소를 1,000으로 나눈 나머지를 출력하는 것 #include #define fio cin.tie(0)->sync_with_stdio(0); using namespace std; #include #inclu..

알고리즘/백준 2022.01.18

백준 BOJ 2824 최대공약수

https://www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 www.acmicpc.net 문제 해설 10억 이하의 수가 최대 1,000개 곱한 수 A, B가 주어질 때, A와 B의 최대 공약수를 구하는 문제다. 주어진 수를 모두 곱하면 int는 물론 long long 자료형의 범위도 벗어나게 되므로 다 곱해서 해결하기엔 무리가 있다. 공약수를 어떻게 구할까? A/B를 단순화시킨다고 생각해보자. 우리는 보통 분수를 단순화 시킬 때, 분자와 분모 ..

알고리즘/백준 2022.01.17

백준 BOJ 9711 피보나치

https://www.acmicpc.net/problem/9711 9711번: 피보나치 첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 P와 Q가 주어진다. www.acmicpc.net 문제 해설 P번째 피보나치 숫자를 Q로 나눈 나머지를 출력하는 문제다. P의 값이 최대 10,000 이다.10,000번째 피보나치 수를 구하면 int 자료형의 표현 범위를 벗어나게 된다.그래서 Q(20억 이하의 자연수)로 나눈 나머지를 구하도록했다. DP를 이용해 P번째 피보나치 수를 구하는 시간복잡도는 O(P)이다.P가 최대 10,000이므로 단순히 구해도 될 것처럼 보인다.이 문제는 그냥 다 구해도 된다.(더 빠른 연산은 https://daan.tistory.com/45을 참고할 수 ..

알고리즘/백준 2022.01.16

백준 BOJ 1948 임계경로

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제 해설 월드 나라는 모든 도로가 일방통행인 도로이고, 사이클이 없다. 출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다. 수많은 사람들이 각각 모든 도로를 지나가며 여행을 할 때, 가장 늦게 오는 경로(들)를 구하는 문제다. 일방통행이고 사이클이 없으므로 어떤 경로로 가는지에 상관없이 갈 수 있는 만큼 쭉~ 가다보면 도착 도시에 도착하게 된다..

알고리즘/백준 2022.01.15

백준 BOJ 4386 별자리 만들기

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해설 n개의 별(1> N; vectorpoint(N); for(int i=0; i > point[i].first >> point[i].second; } //별들 사이의 거리 계산해두기 for(int i=0; i

알고리즘/백준 2022.01.07

백준 BOJ 12850 본대 산책2

https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 12849 본대 산책 문제와 거의 같다. 산책 시간(D)이 매우 커졌을 뿐. 문제 해설 준영이가 정보과학관을 출발해 산책하고 정보과학관으로 돌아오는 데 D분이 걸린다. => D번의 건물 이동 정보과학관에 있던 준영이는 어디로 갈 수 있을까? 전산관, 미래관이다. 미래관으로 갔다면? 그로부터 1분 후에 위치할 수 있는 곳은? 정보과학관, 전산관, 신양관, 한경직기념관이다. 이처럼 위치한 곳에 따라 1분 후에 위치할 곳은 한정적이다. 경우의 수를 살펴보자 now_v[0]을 현재(T) 준영이가 정보과학관에 있는 경우의..

알고리즘/백준 2022.01.05

백준 BOJ 12849 본대 산책

https://www.acmicpc.net/problem/12849 12849번: 본대 산책 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다. www.acmicpc.net 문제 해설 준영이가 정보과학관을 출발해 산책하고 정보과학관으로 돌아오는 데 D분이 걸린다. => D번의 건물 이동 정보과학관에 있던 준영이는 어디로 갈 수 있을까? 전산관, 미래관이다. 미래관으로 갔다면? 그로부터 1분 후에 위치할 수 있는 곳은? 정보과학관, 전산관, 신양관, 한경직기념관이다. 이처럼 위치한 곳에 따라 1분 후에 위치할 곳은 한정적이다. 경우의 수를 살펴보자 now_v[0]을 현재(T) 준영이가 정보과학관에 있는 경우의 수라고 해보자. next_v[0]을 1분 후(T+1) 준영이가 정보과학관에 ..

알고리즘/백준 2022.01.04