고동치는고동

문제 링크 : https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 첫째 줄에 x y w h가 주어진다. w와 h는 1,000보다 작거나 같은 자연수이고, x는 1보다 크거나 같고, w-1보다 작거나 같은 자연수이고, y는 1보다 크거나 같고, h-1보다 작거나 같은 자연수이다. www.acmicpc.net #include #include #define n_ 1005 using namespace std; int n, m; int arr[n_]; char str[n_]; int main(void) { int x, y, w, h; cin >> x >> y >> w >> h; int res = min(x, y); res = min(res, min(w - x, h - ..

문제 링크 : https://www.acmicpc.net/problem/17419 17419번: 비트가 넘쳐흘러 🎶 DJ욱제는 비트에 몸을 맡기는 중이다. 🎶 DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다! N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용� www.acmicpc.net K = K-(K&((~K)+1)) 문제에 나오는 연산을 10110을 대상으로 한번 실행해보자 ~K 는 01001 여기에 1을 더하면 01010 기존의 K와 &연산을 하면 00010 기존에 K에서 이를 빼면 10100 연산을 여러번 반복해보면 알겠지만 위 식은 K라는 이진수에서 마지막 1을 빼는 연산이다 팬윅트리에서 사용되기도 한다. 결국 입력에서 1의 개수를 세는 문제..

문제 링크 : https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 길이가 1인 이친수는 한가지이다. 1 길이가 2인 이친수도 한가지이다. 10 길이가 3인 이친수는 두가지이다. 100 101 길이가 4인 이친수는 세가지이다. 1000 1001 1010 길이가 5인 이친수는 다섯가지이다. 10000 10001 10010 10100 10101 ... 계속 해보면 알겠지만 n-1번째 이친수의 갯수와 n번째 이친수의 갯수에 연관성이 존재한다. ..

문제 링크 : https://www.acmicpc.net/problem/14697 14697번: 방 배정하기 정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 www.acmicpc.net 입력이 1 2 5 50이라고 가정해보자 먼저 확실하게 알 수 있는 것은 전체 인원이 1명, 2명, 5명일 때 빈 침대 없이 배정 가능하다는 점이다. 그리고 2명일 때 완벽하게 배정이 가능하기 때문에 2명에 1명 2명 5명을 더한 3 4 7도 마찬가지로 빈 침대 없이 배정 가능하다. 3 4 7 에서 위의 과정을 계속 반복하면, 12, 17 ... 등등 다양한 수에 대해서 빈침대 ..

문제 링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 1과 달라진 점은 집들이 서로 원형으로 이어져 있어서 점화식이 시작하는 초기 조건을 잡을 수 없다는 것이다. 확실한 것은 첫 번째 집이 적어도 RGB 세 가지 색 중 하나로 칠해져 있다는 것이다. 각각의 색을 한번에 처리하는 것이 아니라 따로따로 구한다면 생각보다 쉽게 처리할 수 있다. 1. 첫번째 집을 R로 칠한다고 가정했을 때 최소 비용 2..

문제 링크 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 당연히 모든 경우의 수를 정말 탐색하면 시간 초과가 난다. 그래서 동적 계획법으로 문제를 해결하기로 했다. 동적 계획법에 있어서 가장 중요한 것은 점화식의 기준이 되는 변수를 잡는 것이다. 이 문제에서는 특이하게 기준 되는 변수가 동전의 개수가 아니라 금액이다. 예시를 통해 알아보자 3개의 동전 1,2,5원을 사용해서 5원을 만드는 경우를 보자 5원을 세가지 동전으로 구성하는 것이 아..

문제 링크 : https://www.acmicpc.net/problem/14469 14469번: 소가 길을 건너간 이유 3 문제 이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다. 농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거 www.acmicpc.net 먼저 소들이 검문소에 오는 순서대로 정렬해준다. algorithm 헤더에 있는 sort 함수를 사용했는데 sort 함수로 구조체를 정렬하는 방법은 아래 글에 설명되어 있다. https://tunafish78.tistory.com/81?category=880339 [STL] algorithm sort 함수 사용법 정렬 PS를 하다보면 데이터를 정렬한 뒤 다뤄야 하는 상..

문제 링크 : https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 � www.acmicpc.net sort 함수를 사용하면 데이터를 정렬할 수 있다. 문제는 데이터가 두개의 값을 기준으로 분류해야 된다는 것이다. 첫번째는 나이, 두번째는 입력 순서 사실 이건 알고리즘 문제라기보다 문법 문제이다. algorithm헤더에 있는 sort함수를 사용함에 있어서 유동적으로 활용할 수 있어야 풀 수 있다. 코드를 읽기전 sort함수의 사용법에 대한 아래 글 부터 읽어보기를 바란다. https..

문제 링크 : 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번째 집..