DAMPER's blog

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 설명 중앙(0), 상(1), 하(3), 좌(2), 우(4)로 된 발판이 있다. 두 발이 같은 지점에 있는 것을 불가능하다. 처음에 양발이 모두 중앙에 위치하고, 발을 이동시킬 때마다 cost가 발생한다. 중앙에서 네방향으로 갈 때 = 2 인접한 발판으로 갈 때 = 3 반대편 발판으로 갈때 = 4 그리고 같은 지점을 한번 더 누를 때는 1 cost가 발생한다...

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Dynamic Programmming 기본 문제들 중 하나이다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 이 때, 이문제는 LCS의 길이만을 출력하는 것이 아닌, 해당 부분 문자열을 찾는 문제이다. LCS를 찾는 점화..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net \( N \times N \) 개의 수가 \( N \times N \) 크기의 표에 채워져 있고 x1행 y1열부터, x2행 y2열까지의 합을 구하는 프로그램을 작성하는 문제. DP 문제로, 1행 1열 부터 자기자신까지의 합을 저장하여 DP 배열을 만든다. \( DP[x][y] = DP[x-1][y] + DP[x][y-1] - DP[x-1][y-1] + A..

출처 : algospot.com/judge/problem/read/NUMB3RS algospot.com :: NUMB3RS 두니발 박사의 탈옥 문제 정보 문제 위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았 algospot.com 위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았습니다. d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수)를 찾아왔습니다. 찰리 교수는 두니발 박사가 감옥에 남겨둔 노트를 분석해 다음과 같은 가설을 세웠습니다. 두니발 박사는 검문을 피해 산길로만 이동한다. 두니발 박사는..

출처: algospot.com/judge/problem/read/ASYMTILING algospot.com :: ASYMTILING 비대칭 타일링 문제 정보 문제 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 algospot.com 타일링 (TILING) 문제에서 좌우 대칭인 경우의 수를 뺀 비대칭 타일링의 갯수를 구하는 문제이다. DP 문제들 중에서 제일 힘들었던 문제인 것 같다...ㅜ 위 문제를 해결하는 방법은 다음과 같다. 1. 대칭인 부분도 포함하여 구한 다음, 대칭인 부분을 빼는 방법. 2. 대칭인 부분을 처음부터 제외하고 구하는 방법. 두 방법 모두 상당한 사고력을 ..

출처 : algospot.com/judge/problem/read/SNAIL algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 algospot.com 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. 여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우..