MingyuPark

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어 https://park-mingyu.tistory.com/38 [백준 1629] 곱셈 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어 $f(n)$을 $x^n$을 계산하 park-mingy..

문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어 $f(n)$을 $x^n$을 계산하기 위해 필요한 최소 계산 횟수라고 하자. $2^16$을 계산하기 위해 필요한 최소 계산 횟수를 구해보자. 직접 계산하면 2를 16번 곱해야 하기 때문에 16번의 계산이 필요하다. 이 경우 n이 2,147,483,647이 되면 계산 횟수가 너무 많아진다. 이럴 때 분할 정복을 이용한다. $f(16)$ = $f(8)+1$ : $2^{16} = 2^8 * 2^8$이기 때문 $f(8)$ = $f(4)+1$ : $2^{8}..

문제 https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 아이디어 한 쪽 물병에 담긴 물을 나머지 모두 붓기 때문에 물병에 있는 물은 2의 거듭제곱(2^x) 으로 표현할 수 있다. K개를 넘지 않는 이라는 표현이 핵심이다. 가능하면 x가 큰 물병이 많은 게 좋다는 뜻이다. 1026개의 물병이 있었다고 해보자. 이 때는 2리터짜리 물병 513개보다는 1024리터짜리 물병 하나와 2리터짜리 물병 하나가 좋다는 뜻이다. (그렇다고 무조건 적은 것을 찾는 게 ..

문제 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 아이디어 각각의 함수를 정의해준다. 최빈값의 경우가 조금 까다로웠다. 각각의 수에 대해 나타난 횟수를 딕셔너리로 정의했다. 각 숫자를 key, 나타난 횟수를 value로 정의했다. 각각의 key, value 조합에 대해서 value가 이때가지 나타난 value의 최댓값보다 큰 경우 해당 숫자가 최빈값이라고 할 수 있기 때문에 max_ 변수를 최빈값의 빈도로 업데이트하고 리스트를 초기화한다. 이 때 빈도가 ..

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 아이디어 N킬로그램에서 필요한 봉지의 수를 f(N)이라고 하자. 이 경우 봉지를 하나 추가하는 경우는 3kg 봉지를 하나 추가하는 경우와 5kg 봉지를 하나 추가하는 경우 둘 중 하나이다. 즉, f(N) = f(N-3) + 1이거나 f(N) = f(N-5) + 1이 될 수 있다. f(N-3)과 f(N-5)의 대소관계를 비교해야 한다. 봉지 수가 가장 적은 경우를 구해야 하기 때문에 f(N-3)과 f(N..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 아이디어 P(N) = P(N-5) + P(N-1)로 나타낼 수 있다. P(N)의 값을 저장해놓고 사용하면 메모리를 절약할 수 있다. 이 때, P(5)까지는 직접 입력해주고 P(6)부터는 점화식으로 표현할 수 있다. Solution t = int(input()) cache = [0 for _ in range(101)] cache[1] = 1 cache[2] = 1 cache[3] = 1 cache[..