고동치는고동

문제 링크 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 사용 알고리즘 : 동적 계획법 0이 출력되는 횟수와 1이 출력되는 횟수를 각각의 DP배열로 해결한다. $F_n$을 n번째 피보나치 수에서 0이 출력되는 횟수라고 가정한다면 다음과 같은 점화식이 세워진다. $$F_n = F_{n=1}+F_{n-2}$$ $F_0$은 1이고 $F_1$은 0이므로 모든 n에 대한 출력횟수를 n번의 연산으로 구할 수 있다. 1에 대한 점화식도 마찬가지로 세울 수 있다. #include int main(void){ int arr[45][2]; arr[0][..

문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 기본적인 틀은 시작시간이 빠른 회의 순서대로 정렬하고 하나씩 보면서 회의를 선택하는 방법이다. 여기서 회의를 선택할 때 고려해야 되는 부분이 두가지 있다. 1. 새로운 회의는 전에 회의가 끝났던 시간보다 늦게 시작해야된다. 2. 1의 규칙을 위반하지 않는 회의들 중 가장 빨리 끝나는 회의를 다음 회의로 선택한다. (시작하는 시간 상관 없이) #include #include #define n_ 100005 using namespace std; struct node{ int s, e; }; bool op..

문제 링크 : https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 모든 사람이 인출하는데 걸리는 시간의 총합이 최소가 되기 위해서는 시간이 적게 걸리는 사람부터 인출을 하면 된다. #include #include #define n_ 1005 using namespace std; int n; int arr[n_]; int main(void){ cin >> n; for (int i = 0; i < n; i++){ scanf("%d", arr + i); } sort(arr, arr ..

문제 링크 : https://www.acmicpc.net/problem/5904 5904번: Moo 게임 문제 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m www.acmicpc.net 예시를 먼저 보면 설명이 더 이해하기 쉬울 것이다. m o o m o o o m o o m o o o o m o o m o o o m o o 재귀적으로 만들어진 세번째 moo 수열이다. 여기서 우리가 전체 문자열의 길이(s)와 중심 개인 문자열의 길이(k)를 알고 있다고 하자 위에서 그 값은 s=25, k=5 이 문자열에서 n번째 문자의 위치는 세가지 ..

문제 링크 : https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 먼저 가장 큰 사각형이 사용할 수 있는 종이이면 사용하고 아닐 경우 9개의 작은 종이들로 나누어 다시 검사한다. 가장 큰 사각형의 변의 길이는 최악의 경우에 3^7이 들어온다. 따라서 사용할 수 있는 종이인지 확인하는데 3^14만큼의 연산 횟수가 소요된다. 만약 사용할 수 없는 종이여서 작은 사각형 9개로 나눠어 검사해도 소요되는 총 연산은 마찬가지로 3^14이다. $$3..

문제 링크 : https://www.acmicpc.net/problem/3036 3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 사용 알고리즘 : GCD 서로 다른 톱니바퀴 A와 B가 맞물려 있을 때 A가 n톱니만큼 돌아가면 B도 n톱니 만큼 돌아가는 것은 당연한 사실이다. A가 a개 만큼의 톱니를 가지고 있고 B가 b개 만큼의 톱니를 가지고 있다고 한다면 A가 한바퀴 회전했을 때(a톱니 만큼 돌아갔을 때) B는 a/b 바퀴 만큼(a톱니 만큼) 돌아간다. 다음으로 구해진 모든 분수를 기약분수로 나타내면 된다. 이는 GC..

문제 링크 : https://www.acmicpc.net/problem/9613 9613번: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 �� www.acmicpc.net 사용 알고리즘: gcd gcd 알고리즘만 알고 있다면 풀 수 있는 간단한 문제이다. 주의할 점은 gcd합이 int범위를 넘어갈 수 있기 때문에 long long으로 선언해줘야 한다는 것이다. 두 값이 모두 1,000,000일 경우 GCD도 1,000,000이 된다. 이러한 쌍이 최악의 경우 100*99/2개 만큼 존재할 수 있으므로 거뜬히 int범위를 벗어난다. 그..

문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net n층 탑이 1에서 3으로 가기 위한 이동 횟수를 $F_n$이라고 하자 n층의 탑을 1에서 3으로 옮기는 순서는 다음과 같다. n-1층의 탑을 1에서 2로 옮긴다 n번째 블럭을 1에서 3으로 옮긴다 2로 옮긴 n-1층의 탑을 2에서 3으로 옮긴다. 결국 아래와 같은 식이 성립한다. $$F_n = 2*F_{n-1}+1$$ 따라서 $F_n$은 $O(n)$안에 구할 수 있다. ..

문제 링크 : https://www.acmicpc.net/problem/14650 14650번: 걷다보니 신천역 삼 (Small) 욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그리고 특히 일�� www.acmicpc.net 먼저 특정 수에 대해 3의 배수인지 판별하는 방법을 알아보자. 각 자리수의 합이 3의 배수이면 3의 배수이다. 270, 999, 531, 8787의 경우를 보면 이 사실이 참임을 알 수 있다. 0, 1, 2를 이용해 구성하는 n자릿수의 경우의 수는 n-1자릿수의 경우에 3을 곱한 값이다. $$F_1 = 2$$ $$F_n = 3*F_{n-1}$$ ..

문제 링크 : https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 필요 알고리즘 : 유클리드 호제법 자연수 A와 B에 대해 A/B라는 분수가 있을 때 이를 기약분수로 형태로 변환하는 문제이다. 두개의 입력되는 분수에 대하여 A와 B를 구하는 방법은 쉽다. 그러나 A/B꼴의 분수를 기약분수로 변환하는 과정에서 문제가 생긴다. 기약분수로 변환하기 위해서는 먼저 A와 B의 최대공약수를 구해야된다. 기존의 방법으로 최대공약수를 구하기 위해서는 min(A, B) 횟수 만큼의 연산이 수행되어야 한다. 입력되는 ..