마탁이의 개발 블로그

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치를 활용한 문제지만 입력과 모듈러 연산이 추가되었다는 점을 주의해야한다. 기존의 피보나치 수 계산 Fn+2 = Fn+1 + Fn (n >= 2)를 그대로 사용하면 시간초과가 발생한다. 찾아보니 행렬연산으로 대체할 수 있었다. 더보기 #include #include using namespace std; // global typedef long long VERYLONG; typedef vector MATRIX; const VERYLONG N_MAX = 1000000000..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 행렬의 곱과 모듈러 연산을 이해하고 구현할 수 있어야 풀 수 있는 문제였다. 또한, N과 B의 입력이 최대 100,000,000,000 까지 주어질 수 있다는 점을 감안한다. 더보기 #include #include using namespace std; // global typedef unsigned long long VERYLONG; typedef vector VECTOR; // method VECT..

https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 간단히 N x M, M x K 두 행렬의 곱을 구하는 문제이다. 더보기 #include #include using namespace std; int main() { // init std::ios::sync_with_stdio(false); // input vector A_Matrix; vector B_Matrix; // A int N = 0; int M = 0; (void)sca..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 기존에는 N / 2 를 이용해 재귀를 했지만 이번 문제에서는 N / 3을 이용해 영역마다의 종이의 개수를 계산한다. 기존 보다 재귀를 하는 영역이 늘어났으며, 결과는 나오지만 586 ms 정도의 수행시간이 걸린다. 채점 현황에 400 ms 이하의 코드들이 있으므로 다시 한번 검토가 필요하다. 더보기 #include #include using namespace std; // global ..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 2630, 색종이 만들기에서 아주 조금 응용하면 풀 수 있다. (응용이 맞나..?) 재귀 + 분할정복의 방법으로 해결한다. '('와 ')'의 삽입 타이밍 또한 생각해 본다. 더보기 #include #include #include using namespace std; // global string answer; vector board; enum QUAD { e_Zero = 0, e_On..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할 정복 단계에서 맨 처음 풀게된 문제이다. 재귀를 이용한 분할 정복으로 생각하고 문제의 해결방법을 생각해본다. 처음에는 사각형의 왼쪽 위, 오른쪽 아래가 필요할 줄 알았으나 왼쪽 위 좌표만 있어도 충분했다. 더보기 #include #include using namespace std; // global int whiteCnt; // 0 int blueCnt; // 1;..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 조합의 출력을 10,007로 나누어야 하는 문제이다. 계산과정에서 나온 값들은 dpArray 혹은 dpDictionrary에 저장하는 식으로 진행하면된다. 값들은 모두 10007 나머지 값들을 사용하면 간단히 구할 수 있다. 더보기 # 25, 12 -> 5200300 N, M = map(int, str(input()).split()) dpDict = dict(); dpDict[0] = 1 dpDict[1] = 1 # r! rFact = 1 if M % 10007 in..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 백준 1676의 팩토리얼 0의 개수를 응용하는 문제라고 생각된다. 2와 5의 개수를 구해야한다. (10을 만들 수 있는 수) 분자의 2나 5의 개수는 증가 시키고, 분모는 개수에서 뺴야한다. 그리고 출력은 2와 5개수 중에서 작은 수를 출력한다. 더보기 # 25, 12 -> 5200300 N, M = map(int, str(input()).split()) cnt5 = 0 cnt2 = 0 num = 2 while True: if(num > N): break ..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 조합을 활용할 수 있어야 한다. 머리에 모자하나만 얹어놔도 된다. 각 옷의 type마다 입지 않았을 경우도 있다는 것을 고려하면 해결할 수 있다. 마지막에는 다 벗었을 경우를 결과에서 차감하였다. 더보기 testCase = int(input()) for tc in range(testCase): N = in..

https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 간단한 판별 문제이다. 더보기 import sys input = sys.stdin.readline ''' 첫 번째 숫자가 두 번째 숫자의 약수라면 factor 배수라면 multiple 둘 다 아니라면 neither ''' answerList = [ 'factor', 'multiple', 'neither'] while(True): testCase = list(map(int, str(input()).split())) if 0 == testCa..