Devlog

10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 배열 A의 구간 합 중에 M으로 나누어 떨어지는 구간을 구하는 문제 입니다. "구간 합"이니까 누적합 배열을 만드는 것 까진 좋은데 여기서 해당 조건에 맞는 구간 찾는다고 일일히 경우의 수를 대입하면 (N(N-1))/2 = N^2이라는 시간이 걸리기 때문에 시간초과가 발생합니다. 다른 방법을 생각해 봐야 합니다. 우선 백준에 걸려 있는 예제를 봅시다. 5 3 1 2 3 1 2 5개의 요소가 주어진 배열에 3으로 나누..

2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 승환이가 지시에 따라 두 발을 딛을 때, 드는 최소의 힘 을 구하는 문제 입니다. 발은 두개이고, 발판은 5개 밖에 안되니 마치 비용이 상대적으로 적은 발로 발판은 딛는 방법을 생각할수 있으나 이는, 4+1+1+1 비용이 들 것을 1+3+3+3 으로 들어 오히려 더 힘들게 게임을 끝내는 경우가 있기 떼문에 그리디로는 풀 수 없습니다. 그렇다면 하나의 발판을 두 발 중 하나가 딛는 경우로 BFS 방법 밖에 없는데, 그렇다고 해서 ..

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차원 배열을 일일히 탐색해서 두 변 이상이 노출되면 치즈를 없애는 방향으로 반복하면 풀리는 문제 처럼 보이겠지만, 조건이 하나 더 붙어 있습니다 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않은 것으로 간주한다. 치즈 내부에 있는 비어있는 부..