Devlog

백준에서 타일 채우기 문제는 2개가 있습니다. 하나는 너비의 범위가 30 이하이고 다른 하나는 10^18입니다. 1탄 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net N = 2일 때 깔 수 있는 타일의 형태를 그려봅시다. 접근 N = 2일 때 둘 수 있는 경우의 수는 총 3입니다. 이렇게 보면 N = 1일 때의 경우의 수는 존재하지 않습니다. 그 이유는 높이가 3이기 때문에 타일의 각도가 [세로, 가로], [가로, 세로] 혹은 [가로, 가로, 가로]입니다. N = 1에 맞게 깔려면 오직 세로 형태만 깔아야 하는데 이때 세로의 길이는 항상 짝수가 되므로 높이가 3인 경우에는 N = 1 형태로 깔 수가 없습니다. 결국 깔린..

내가 당분간은 그래프, 트리 문제 안푼다고 했는데... 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제 민식이 부터 말단 사원 까지 소식을 전파했을 때 걸리는 시간의 최솟값을 구하는 문제 입니다. 착각하기 쉬운 점이 있다면 현재 위치의 간부가 부하들에게 전파를 할 때, 모든 부하들을 전파한 다음, 부하들이 전파를 하는 것이 아니라 간부가 부하 1명에게 전파를 하면 그 다음에는 간부가 아직 전파하지 않은 부하에게 전파함과 동시에 이미 전파된 부하도 같이 자신의 부하에게 전파를 하게 됩니다. 아래의 그림 처럼요...

그동안 그래프 문제만 풀어대서 문제해결력 향상 + 코드포스 준비를 위해 다이나믹 프로그래밍과 그리디, 수학 위주로 문제를 풀고 있습니다. 너무 안해서 그런지 쉬운것부터 시작하는데도 빌빌거리네요. 마치 1년전 그래프로 빌빌거렸던 시절과 똑같은거 같습니다. 예나 지금이나 실력이 늘지 않는군요 ㅠㅠ 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 1부터 N까지 번호가 랜덤하게 나열되어 있습니다. 이 번호들을 오름차순으로 나열할 때, 이동되는 번호들의 최소 갯수를 구하는 문제 입니다. 그러니까 어느 번호가 옮겨지는 지, 어..

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이전 문제인 다리 만들기 1이 여러 개의 섬들 중, 두 개의 섬을 잇는 다리의 최소 길이를 구하는 문제였다면. 2탄은 모든 섬들을 잇는 다리 길이의 합의 최솟값을 구하는 문제입니다. 구현 폭탄에 그래프 종합 문제라 다리 만들기보다는 난이도가 더 높게 책정되어있긴 한데, 저한테는 1탄보다 2탄이 더 쉬웠습니다. 1탄을 아마 거의 1년 전에 풀었던 거 같은데, 그 당시 그래프 알고리즘은 커녕 DFS, BFS에서도 빌빌거렸던 시절이라 더 어려워 보..

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 방법 밖에 없는데, 그렇다고 해서 ..