등반

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..

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를 단순화시킨다고 생각해보자. 우리는 보통 분수를 단순화 시킬 때, 분자와 분모 ..

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을 참고할 수 ..

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

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

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) 준영이가 정보과학관에 있는 경우의..

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) 준영이가 정보과학관에 ..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2749, 11444 2749 문제 해설 재귀나 반복 문제를 풀다 보면 한 번쯤 만나는 피보나치의 수에 관한 문제다. 그런데 입력 값 n의 범위가 1~10^18사이의 정수다. 너무 크다. 그래서 1,000,000으로 나눈 나머지를 출력하라고 한다. 정해는 피사노 주기를 이용하는 것 같다. 본인은 일단 구해야 하는 피보나치의 수는 모두 구했다. 일단, 피보나치의 수를 살펴보자 Fn = Fn-1 + Fn-2 (n ≥ 2) 이렇게 생겼다. 단순 재귀를 이용한 풀이는 원하는 수를 구하..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 해설 부분 문자열은 한 문자열에서 연속한 부분을 떼어낸 문자열이다. 주어진 문자열 중 긴 문자열에 더미 문자열을 붙이고 완전탐색 시켰는데 통과했다... 얼떨떨했따... 긴 문자열의 비교 시작 부분을 이동시키며, 작은 문자열의 길이만큼 비교했다. #include #define fio cin.tie(0)->sync_with_stdio(0) using namespace std; int ..

https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 문제 해설 1. 나3 : x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다. 2. 곱2 : x를 2로 곱한다. 어떤 수 x에 1, 2 두 가지 연산을 N번 시행했을 때, 수열 A가 나온다. 이 수열 A의 순서를 뒤섞은 수열 B로부터 A를 찾아내는 문제다. 살펴볼 것 1. 주어진 수열에 있는 원소는 중복이 있을까? 중복은 없다. 연산은 3으로 나누거나 2로 곱하는 것뿐이다. ..