Devlog

1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 결국엔 힌트를 보고 풀었습니다. 구현까진 어떻게 했는 데, TLE에서 더 이상 버티지 못했습니다. NMK를 풀 수 있었던건, 정답을 맞추면 되는 문제였지만 이 문제는 최적화 까지 요구를 했었기 때문에 중간에 주저앉아 버린 것 같군요. N크기의 체스판, 몇 개의 장애물에 비숍을 세울 수 있는 크기를 구하는 문제로, 그냥 보면 단순히 백트래킹 돌리면 되어 보이는 문제 이지만 실상은 그렇지 않습니다. 바로 TLE가 뜨기 때문에 좀더 빠른 시간 안에 구하는 방법을 찾아야 합니다..

솔직히 풀다가 진짜 열도 받고 풀이 보고 싶은 욕망이 초단위로 들긴 했는데 그래도 참고 하니까 풀리긴 하네요. 문제 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net N: 1부터 N까지 들어있는 수열 M: 가장 긴 증가하는 부분 수열의 길이 K: 가장 긴 감소하는 부분 수열의 길이 이 세가지 조건에 충촉되는 수열을 구하는 문제 입니다. 접근 주어진 조건에 수열을 만드는 공식을 세우는 구성적 접근과 할 수 있는 데 까지 조건에 맞는 수열을 만들어 내야 하는 그리디 알고리즘 의 조합을 이루는 문제 입니다. 따라서 이 문제를 풀기 위해 저는 아래와 같이 접근을 시도했습니다. 최대한 수열을 만들도록 노력해야 하기 때문에, N,M,K이 세 값으로 수열이 될 수 있는 최..

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 문제 배열 A의 부분 구간의 합과 배열 B의 부분 구간의 합, 이 두개의 합이 T와 일치하는 경우를 구하는 문제 입니다. 접근 각 배열 A,B에서의 부분합이 될 수 있는 수들을 나열합니다. 부분합이 될 수 있는 수들을 모은 배열은 각각 SA, SB라고 합시다. 그렇다면 SA를 순회하면서 SB의 요소 중에 T-SA[i]와 일치하는 값을 찾으면 됩니다. ans

2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 접근 MxN 크기의 판에 놓여 있는 치즈들이 전부 녹아 없어지는 데 걸리는 시간을 구하는 문제 입니다. 치즈가 녹아 없어지는 조건이 두 개 이상의 변이 외부 공기에 노출되어 있는 경우 입니다. 그렇다면 2차원 배열을 일일히 탐색해서 두 변 이상이 노출되면 치즈를 없애는 방향으로 반복하면 풀리는 문제 처럼 보이겠지만, 조건이 하나 더 붙어 있습니다 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않은 것으로 간주한다. 치즈 내부에 있는 비어있는 부..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 접근 BFS를 활용한 전형적인 시뮬레이션 문제 입니다. 풀이 방법은 크게 보면 간단합니다. 상어 주변에 먹을 수 있는 물고기 들을 BFS를 이용해 탐색합니다. 먹을 수 있는 물고기들 중 조건에 맞는 물고기를 찾아 먹은 다음, 상어를 그 위치로 이동합니다. 먹을 수 있는 물고기가 더 이상 없을 때 까지 반복합니다. 조건 딱 봐도 간단해 보이는 문제이지만 난이도가 무려 골드3으로 책정되어 있는 이유는 바로 2번에서 덕지덕지 붙어있는 조건 때문입니다. 문제에서 ..

5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 이렇게 풀면 망한다. I와 O만 이루어진 문자열에서 IOI패턴이 들어있는 패턴 문자열이 몇 번 일치하는 지 구하는 문제 입니다. 문자열 길이가 N이고, 패턴의 길이가 M(M은 3 이상의 홀수) 라고 할 때, 브루트 포스 방식으로 문자를 하나씩 순회할 때마다 일일히 패턴 길이를 순회해서 일치하는 지 검사를 하게 되면 O(N*M)의 시간이 걸리게 되므로 시간 초과가 발생합니다. 패턴의 정보를 활용 ..