고동치는고동

문제 링크 : https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 수학 문제라기보다 예외처리 문제에 가까웠다. 입력이 3개 이상일 때 a와 b를 구하는 방법은 간단하다. $$x_1 * a + b = x_2$$ $$x_2 * a + b = x_3$$ 위 두 식을 연립해서 a와 b를 구할 수 있다. a와 b를 구했다면 문제에서 요구하는 다음 숫자도 쉽게 구할 수 있다. 이제 예외 상황들을 하나씩 살펴보자. 1. 입력이 하나일 때 다음 수를 알 수 없으므로 A를 출력한다. 2. 입력이 두개일 때 입력이 두개일 때는 만약..

문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 총 N개의 집이 있을 때, i번째 집을 칠하는 경우의 수는 총 3가지이다. 빨강, 파랑, 초록 똑같은 색은 이웃할 수 없다는 조건이 없다면 순서대로 가장 저렴한 색으로 칠하면 되지만 이웃한 집은 다른 색으로 칠해야 되므로 문제가 복잡해진다. 가장 먼저 빨간색으로 i번째 집을 칠하는 경우의 수를 생각해 보자. i번째 집이 빨간색으로 칠해지지 위해서는 i-1번째 집..

문제 링크 : 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)$안에 구할 수 있다. ..