아롱이의 PS하는 블로그

https://www.acmicpc.net/problem/18940풀이먼저 지난번에 올린 스프라그-그런디 정리(이하 스그정리)에 관한 글을 읽어보고 오면 도움이 많이 된다. 13034번 문제와 비슷하다.먼저 N = 0일때는 그룬디 수가 0(패배상태이므로)N = 1, 2일때는 그룬디 수가 1이다. 단 한번의 행동으로 무조건 패배상태로 만들 수 있으므로 이 경우는 마음대로 그룬디 수를 1로 잡아도 좋다. N이 3 이상일때는, 어떤 임의의 부분에서 연속된 최대 3개의 카드를 제거함으로 인해 보드판이 두 개로 나뉜다.가령 다음과 같다.N = 6일때 3을 골랐다고 해보자. 이제 보드판은 (1) 부분과 (5, 6) 부분 두 개로 나누어졌다. 이 상태는 grundy[1]과 grundy[2]의 님 합으로 표현할 수 있..

https://www.acmicpc.net/problem/20544풀이풀고 나서 보니까 많은 분들이 2차원, 혹은 4차원(!) dp를 구현하여 고통을 호소하고 계셨다.허나 이 문제는 단순 수학 점화식 풀듯이 일차원 dp로 쉽게 풀 수 있다.(이걸로 숏코딩도 쉽게 할 수 있다)아래에서는 그 풀이를 소개하고자 한다. 구하고자 하는 값을 $a_n$이라고 하자.$a_n$은 마지막 부분에 어떤 종류의 장애물이 오느냐에 따라 아래와 같이 점화식으로 표현 할 수 있다.근데 그냥 단순히 $a_{n}=a_{n-1}+2\times a_{n-2} +3\times a_{n-3}$ 라고 표현하면 빨간 글씨처럼 '누락되는 부분'이 있다. 바로, 0101101.....02와 같이 마지막 부분 전까지는 0과 1과 나오는 상황이다. ..

https://www.acmicpc.net/problem/11717풀이바로 이전에 스프라그 - 그런디 정리 소개글을 쓰고 왔다.이 문제도 스그정리를 써서 풀 수 있다. 하나 깨달은 점은, 기존과 달리 2차원 게임에서, 각각의 '칸'에 그룬디 수를 정의할 수 있을 뿐만 아니라, 그냥 어떤 게임판의 일부분 그 자체가 그룬디 수 화 될 수 있음이다. 일단 한 가지 간단한 관찰을 하고 들어가보면, 벽과 x를 따로 구분하기 어려우니까 그냥 벽이 설치되는 것이 아니라 x가 설치되는 것이라고 생각해도 좋다.(사실 근데 크게 별로 상관은 없다.) 4차원 dp에다가 각 보드의 부분의 그룬디 수를 저장할 수 있다.dp 형식은 #dp[x1][y1][x2][y2]는 (x1, y1)부터 (x2, y2)까지의 보드의 Grundy..

서론게임 이론에서 게임의 현재 상태를 분석하기 위해 쓰는 스프라그 - 그런디 정리.백준에서 날먹이라는 말이 있다. 어떤 이론이길래 그렇게 쉽게 되는 것일까? 솔직히 말해서 완벽하게 이 이론을 이해하려면 어렵다고 본다.....구현 자체가 쉽기 때문에 날먹이라는 말이 있는 것 같다.따라서 오늘 이 글에서는 스프라그 - 그런디 정리를 내가 이해한 바에 따라 쉽게 설명해보고자 한다. 게임 상태가장 먼저, 게임의 '상태'라는 것을 이해하고 넘어가자.여러분들은 모두 어릴 적 '베스킨라빈스 31'이라는 게임을 들어본 적이 있을 것이다.게임의 규칙은 다음과 같다.선공과 후공이 번갈아가며, 1부터 시작하여 연속한 자연수를 1~3개 부른다. 31을 부르게 되는 사람이 진다. 수학을 좀 해본 사람들이라면(꼭 굳이 그렇지는 ..

https://www.acmicpc.net/problem/8481 소요시간: 3일풀이이 문제를 왜 만들었을까?아주 간@단한 문제이다! 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 주어지면 그에 걸맞는 출력만 하면 된다!! 0번 #구현더보기ONTAK 2010를 출력하면 된다. 소요바이트: 19바이트1번#압축 #구현 #파싱더보기10개의 데이터들 중에서 길이가 가장 길다.같은 알파벳이 반복되므로, G#2932#o#2931....과 같이 해당 문자와 등장 횟수를 미리 계산해서 문자열로 만든 후 출력하였다. 여담으로 반복을 줄인 원문은 해당 대회의 Godzilla라는 문제이다. + 반복되는 횟수가 계차수열이다. 숏코딩할 때 이용할 예정이다. 소요바이트: 13922바이트2번#구현더보기피보나치 수열을..

https://www.acmicpc.net/problem/1533풀이인접 행렬의 특징으로는,A[i][j]가 정점 i에서 정점 j로 갈 수 있는 길의 개수라고 하면A를 t번 거듭제곱한 행렬의 [x][y]는, 길을 t개 거쳐서 정점 x에서 정점 y까지 가는 경로의 개수이다.여기서 알 수 있다 다만 이 문제에서는 길에 가중치가 있다. 단순히 주어진 행렬을 T번 곱한다고 해서 답이 나오지 않는다. 12850처럼 문제를 해결해주기 위해서, 인접행렬의 모든 원소를 1로 만들어주는 전략을 세우기 위해그래프의 형태를 조금 바꿔주자! 길을 가는데 걸리는 시간이 1, 2, 3, 4, 5중 하나이므로 우리는 다음과 같은 전략을 세울 수 있다. 예를 들어 정점 2에서 1로 가는데 3분이 걸린다고 하자.정점 1을 이제 1, 1..

https://www.acmicpc.net/problem/18122https://www.acmicpc.net/problem/27743풀이충분히 찍어서 맞출 수 있는 문제이다. 일단 일반적으로 하노이 탑 N개를 옮기는 최소 횟수는 $2^{N} - 1$회임이 잘 알려져있다.그런데 18122번 문제와 같은 경우는 어떻게 하면 좋을까? 일단 N = 1일 때를 살펴보자. 그림과 같이 3회를 옮기면 됨을 알 수 있다. N = 2일 때는 어떨까? 일단 위에 쌓여있는 쪼그만 놈들은 무시하고, 큰 1, 2번 판이 어떤 움직임을 보여야 하는지 생각해보자. 그러면 N = 1일때와 마찬가지의 방법으로 3번 움직여야 함을 알 수 있다. 이제 쪼그만 놈들의 움직임을 보자. 큰 판들이 위와 같이 잘 움직일 수 있게 쪼끄만 놈..

https://www.acmicpc.net/problem/1086풀이모든 순열을 따져봐야한다. N이 15밖에 안되므로, 단순이 모든 순열을 따져주면 되지 않나? 싶지만 15팩토리얼은 1,307,674,368,000이라는 큰 숫자다. 따라서 다른 방법을 찾아보자. 조금만 생각해보면 비트마스킹을 이용할 수 있다! $2^{15}$가 32,765이기 때문이다. dp식을 다음과 같이 세워보자.dp[mask][r] = 현재 상태에 있는 수들을 어떤 순서로 나열했을 때 만들어지는 수의 나머지가 r인 경우의 수 어떤 수를 이미 만들어진 수 뒤에 추가로 붙이면 나머지는 어떻게 변하는가?예를들어 새로 붙일 수가 4자리 수라고 하자.그러면 기존 수에 10,000을 곱하고 새로 붙일 수를 더하는 것과 마찬가지다.그러면 나머지..

https://www.acmicpc.net/problem/1106풀이dp 문제이다.dp에 많이 약해서 dp 연습을 이제 좀 시작하려고 한다.얼마나 약하냐면, 골드 4인데도 dp 식이 아직 잘 안떠오른다. dp리스트는 1차원으로, dp[i] = (정확히 i명 모으는데 드는 최소 비용)이다.초기에 i = 0을 제외하고는 전부 무한대로 초기화한다.한 번에 최대 100명까지 들어올 수 있으므로 dp의 길이는 C+100정도면 충분할 것이다.각 도시별로 다음을 반복하면 된다.j가 0부터 C+100-gain 인 동안,dp[j+gain] = min(dp[j+gain], dp[j] + cost) 이게 되는 이유는, j가 0부터 점점 커지므로, 중복이 자연스럽게 카운팅된다. (직접 그려보면 안다.) #include usi..

https://www.acmicpc.net/problem/16995풀이이전 포스팅에서 다룬 신발끈 공식의 특성을 창의적으로 이용하는 문제이다. 처음에는 이런 생각을 했다.볼록 K각형은 K-2개의 삼각형으로 이루어져있음을 이용해서"대칭적으로, 가능한 모든 조합의 삼각형을 다 더했을 때 전체 다각형의 넓이와 관련해서 간단하게 식이 나오지 않을까?" 안나왔다. 이것때문에 몇시간을 고민했다.사실 나오긴 나오는데 이걸 수학적으로 계산하려니 머리가 아팠다. 그래서 조금 다른 접근을 소개한다. 신발끈 공식과 넓이 계산 예를 들어서 N = 6, K = 4라고 해보자.즉, 육각형(여섯모) 내에서 4개의 점을 잡아 사각형(네모)를 만드는 것이다. 예를 들어서, A, C, D, F의 사각형을 골랐다고 해보자.그러면 우리는 ..