고양이 두 잔

목차 이진 탐색 [Java+Python]1920번, 수 찾기 [Java+Python]1654번, 랜선 자르기 [Java+Python]2805번, 나무 자르기 [Java+Python]2805번, K번째 수 [Java+Python]12015번, 가장 긴 증가하는 부분 수열 2 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 $x_1, ..., x_N$이고, 집 여러 개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당..

목차 문제 1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)x100원의 상금을 받게 된다. 모두 다른 눈이 나오는 경우에는 (그중 가장 큰 눈)×100원의 상금을 받게 된다. 예를 들어, 3개의 눈 3, 3, 6이 주어지면 상금은 1,000+3×100으로 계산되어 1,300원을 받게 된다. 또 3개의 눈이 2, 2, 2로 주어지면 10,000+2×1,000 으로 계산되어 12,000원을 받게 된다. 3개의 눈이 6, 2, 5로 주어지면 그중 가장 큰 값이 6이므로 6×100으로 계산되어 600원을 상금으로 ..

목차 문제 흔한 수학 문제 중 하나는 주어진 점이 어느 사분면에 속하는지 알아내는 것이다. 사분면은 아래 그림처럼 1부터 4까지 번호를 갖는다. "Quadrant n"은 "제 n사분면"이라는 뜻이다. 예를 들어, 좌표가 (12, 5)인 점 A는 x좌표와 y좌표가 모두 양수이므로 제1사분면에 속한다. 점 B는 x좌표가 음수이고 y좌표가 양수이므로 제2사분면에 속한다. 점의 좌표를 입력받아 그 점이 어느 사분면에 속하는지 알아내는 프로그램을 작성하시오. 단, x좌표와 y좌표는 모두 양수나 음수라고 가정한다. 입력 첫 줄에는 정수 x가 주어진다. (−1000 ≤ x ≤ 1000; x ≠ 0) 다음 줄에는 정수 y가 주어진다. (−1000 ≤ y ≤ 1000; y ≠ 0) 출력 점 (x, y)의 사분면 번호(1..

목차 이진 탐색 [Java+Python]1920번, 수 찾기 [Java+Python]1654번, 랜선 자르기 [Java+Python]2110번, 공유기 설치 [Java+Python]2805번, K번째 수 [Java+Python]12015번, 가장 긴 증가하는 부분 수열 2 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할 것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그다음, 한 줄에 연속해 있는 나무를..

목차 이진 탐색 [Java+Python]1920번, 수 찾기 [Java+Python]1654번, 랜선 자르기 [Java+Python]2805번, 나무 자르기 [Java+Python]2110번, 공유기 설치 [Java+Python]2805번, K번째 수 [Java+Python]12015번, 가장 긴 증가하는 부분 수열 2 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm..

목차 이진 탐색 [Java+Python]1654번, 랜선 자르기 [Java+Python]2805번, 나무 자르기 [Java+Python]2110번, 공유기 설치 [Java+Python]2805번, K번째 수 [Java+Python]12015번, 가장 긴 증가하는 부분 수열 2 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정..

목차 분할 정복 단계 [Java+Python]2630번, 색종이 만들기 [Java+Python]1992번, 쿼드 트리 [Java+Python]1780번, 종이의 개수 [Java+Python]1629번, 곱셈 [Java+Python]11401번, 이항 계수 3 [Java+Python]2740번, 행렬 곱셈 [Java+Python]10830번, 행렬 제곱 [Java+Python]11444번, 피보나치 수 6 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 아래 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각..

목차 분할 정복 단계 [Java+Python]2630번, 색종이 만들기 [Java+Python]1992번, 쿼드 트리 [Java+Python]1780번, 종이의 개수 [Java+Python]1629번, 곱셈 [Java+Python]11401번, 이항 계수 3 [Java+Python]2740번, 행렬 곱셈 [Java+Python]10830번, 행렬 제곱 [Java+Python]6549번, 히스토그램에서 가장 큰 직사각형 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 $F_n = F_{n-1} + F_{n-2} (n ≥ 2)$가 된다. $n=17$일 때까지 피보나치 수를 써보..

목차 분할 정복 단계 [Java+Python]2630번, 색종이 만들기 [Java+Python]1992번, 쿼드 트리 [Java+Python]1780번, 종이의 개수 [Java+Python]1629번, 곱셈 [Java+Python]11401번, 이항 계수 3 [Java+Python]2740번, 행렬 곱셈 [Java+Python]11444번, 피보나치 수 6 [Java+Python]6549번, 히스토그램에서 가장 큰 직사각형 문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,0..

목차 분할 정복 단계 [Java+Python]2630번, 색종이 만들기 [Java+Python]1992번, 쿼드 트리 [Java+Python]1780번, 종이의 개수 [Java+Python]1629번, 곱셈 [Java+Python]11401번, 이항 계수 3 [Java+Python]10830번, 행렬 제곱 [Java+Python]11444번, 피보나치 수 6 [Java+Python]6549번, 히스토그램에서 가장 큰 직사각형 문제 N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오. 입력 첫째 줄에 행렬 A의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이..