문제 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 이 문제는 '11053번 가장 긴 증가하는 수열' 문제와 유사하지만 입력 범위가 크기 때문에 DP로 풀이하면 시간초과가 발생한다. 대신 LIS를 구하는 다른 방법인 이분 탐색을 활용해 풀이해야한다. 우선 입력 받은 수열을 가장 긴 증가하는 수열로 만드는 방법을 확인해보자. 어느 수열의 첫 5개의 원소가 [30, 35, 40, 10, 20, ...]일 때 현재까지의 LIS는 [30, 35, 40]이 될 것이다. 여기서 이 LIS는 수열의 다음 원소들에 따..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP를 활용하여 해결할 수 있으며 주어진 예제 입력을 dp 배열로 메모이제이션한다면 다음과 같다. arr 10 20 10 30 20 50 dp 1 2 1 3 2 4 10은 10보다 작은 값이 없기 때문에 길이가 1인 수열이 되고, 50은 10, 20, 30, 50으로 길이가 4인 수열이 된다. 이를 DP로 해결하기 위한 반복문을 만들어보자. 입력 받은 배열을 순회하며 각 원소..

문제 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이 for문을 통해 입력받은 배열을 탐색하며 각 위치에서 현재 색상을 기준으로 아래쪽이나 오른쪽을 바꾸어 가며 확인해주면 된다. 연속된 동일한 색을 찾는 함수에서는 가로 방향과 세로 방향으로 색을 확인해 준다, 코드 import kotlin.math.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() // 오른쪽, 아래로 이동하는 배열 val dx = arrayOf(1, 0) val dy = arrayOf(0, 1) val num = br.readLine().toI..

문제 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 8 X 8 크기의 확인용 배열을 활용하여 입력받은 체스판 배열에서 최소값을 찾아내면 된다. 최소값을 찾는 방법은 for문을 통해 해당 배열의 각 칸을 확인하고, 해당 칸이 홀수 자리에 있는지 짝수 자리에 있는지 확인한다. 그리고 그 칸이 'B'인지 'W'인지를 판별하여 자리에 맞지 않는 색일 경우 값을 증가해주면 된다. 코드 import java.util.* import kotlin.math.* fun main() { val br = Syste..

문제 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 풀이 지그재그 순서의 분수를 차례대로 나열하고 열 별로 살펴보면 규칙성을 찾을 수 있다. 1열: 1/1 2열: 1/2 2/1 3열: 3/1 2/2 1/3 4열: 1/4 2/3 3/2 4/1 5열: 5/1 4/2 3/3 2/4 1/5 1열의 분모 + 분자 = 2, 2열의 분모 + 분자 = 3인 것처럼 각 열마다 분자와 분모를 더하면 열의 값 + 1이 된다. 이 규칙을 활용해 입력받은 숫자가 몇 번째 열에 속하는지 계산할 수 있다. 분모와 분자를 더한 값을 나타내는 sum 변수와 분수의 순번을 나타내는 tmp변수를 선언한다. while문을 통해 tmp가 입력받은 num보다 작을 때까지 tmp..