아롱이의 PS하는 블로그

https://www.acmicpc.net/problem/10754랜마에 뜬 거의 아무도 안 푼 문제인데 풀고나니 재미있었다.풀이입력으로는 =(무게가 같다)와 무게가 큰 관계들을 토대로 위상정렬틱하게 순서들을 정리해보아야 할 것 같다.그 전에, = 쿼리를 먼저 처리해주어서 무게가 같은 동전들은 분리 집합 자료구조를 이용해 미리 같은 그룹으로 묶어놓도록 하자. 다음으로 한꺼번에 이제 우리는 이 DAG에서 '가장 긴 경로'의 길이가 N과 같을 때, 그 경로에 포함된 모든 노드들은 동전의 종류가 확정된다는 것을 알 수 있다. (그 외의 동전들은 전부 ?(미정)이다.)그러니까 결국에는 DAG에서 가장 긴 경로와, 그 경로에 포함된 노드들을 효율적으로 구하는 것이 이 문제의 핵심이 될 것이다. 여기서 좀 애를 먹..

https://www.acmicpc.net/problem/1014풀이맨 윗줄부터 아래로 내려가면서 dp할 것이다.가로 길이가 최대 10밖에 안되므로 비트마스킹을 해서, 현재 행에 배치할 수 있는 학생 조합 마스크들을 구해놓자.dp 정의는 dp[행번호][마스크] = (현재행번호까지 봤을 때 최대학생수)이다.i번째 행을 살펴볼 때 가능한 마스크에 대해서 i-1번째 마스크들과 직접 비교해주며 가능한 경우 최댓값을 갱신해주면 된다. import sysinput = sys.stdin.readlineC = int(input())for t in range(C): N, M = map(int, input().split()) graph = [] for i in range(N): s = inpu..

https://www.acmicpc.net/problem/13141풀이불을 N번 정점에서 붙인다고 하자.불길이 어떤 정점에 도달하는 시간은 최단거리 알고리즘을 이용하면 구할 수 있다.A, B를 잇는 길이 L인 간선이 다 타는데 걸리는 시간은 (dist[N][A] + dist[N][B] + L)/2 이다.N과 M이 충분히 작으므로 플로이드-워셜 알고리즘과 브루트포스 알고리즘을 이용하면 답을 구할 수 있다.시간복잡도는 O(N^3 + MN)이다. import sysinput = sys.stdin.readlineINF = 9_999_999N, M = map(int, input().split())dist = [[INF]*(N+1) for _ in range(N+1)]lines = []for i in range(M..

https://www.acmicpc.net/problem/32374 들어가기에 앞서...이제는 대학생이 되었다.고등학교때 디코에서만 보던 멋진 분들을 어느새 내 카톡 친구창에서 보게되었다.이제 진짜 열심히 할 때가 되었다.풀이문제를 잘 읽어보면 선물 상자에 모든 선물을 담을 수 없는 경우는 입력으로 주어지지 않는다고 하였다.그말인즉슨 선물 상자에 반드시 모든 선물을 다 담을 수 있다. 그러니까 선물들과 선물상자를 크기순으로 쭉 정렬해보면$a_i$ 선물은 반드시 $b_i$ 안에 들어갈 수 있다. 문제에서 주어진 예제를 예시로 들면 아래 그림과 같다. 선물의 크기가 상자의 크기 이하여서 상자에 들어갈 수 있는 경우를 파란색 화살표로 표현하였다. 만약 파란색 화살표가 아래 그림과 같이 오른쪽으로 기울어져있다면..

https://www.acmicpc.net/problem/18790풀이1번째 시도(시간초과/메모리초과)일단, 주어진 리스트에서 각 수가 몇 번 등장하는지를 센다.가장 먼저 떠오른 건 DP. 대충 N의 범위가 500이니까 인자를 3개 잡는 재귀함수 형식으로 짜자.인자는 다음과 같다. dp[현재 처리하는 수][현재까지 쓴 수의 개수][현재 나머지] 마지막에 dp[N-1][N][0]을 불러서, 정답에 도달할 수 있는지 본다. dp 함수의 리턴값은 [현재 처리하는 수]가 몇 개 쓰였는지이다.이 값을 이용해서 역추적할 수 있다. 랜덤하게 생성해낸 데이터에 대해서 잘 돌아가였고, 자신만만하게 제출하였으나,,,, 2번째 시도(시간초과/메모리초과)dp 인자를 바꿔볼까?주어진 리스트에서 각 수의 등장 횟수를 카운트하는..

먼저 아래 문제를 보자. https://www.acmicpc.net/problem/22935 문제를 읽어보면 N이 주어질 때 N번째 외치는 수는 과연 무엇이 되어야 하는가를 구하는게 일단 어렵다. 그래서 표를 한 번 그려보았다.주기는 (15 - 1) * 2 = 28이다. 그런데 28로 나눈 나머지 안에서도 절반은 증가하고 절반은 감소하기 때문에14로 나눈 몫이 홀수인지 짝수인지에 따라 경우를 나눴다. 지금까지는. 이렇게 탄생한 지금까지의 나의 코드는 대충 아래와 같이 복잡하다. 매번 절편을 계산해줘야하고 보정해야해서 표를 맨날 그리기때문에 머리아프고 손아프며 시간이 걸린다. 그러나 아래와 같은 아주 간단한 방법이 있음을 깨달았다. 이렇게 28개씩 묶으면 사이클이 생긴다.그래서 미리 다음과 같은 리스..

https://www.acmicpc.net/problem/13460 들어가기에 앞서...오랜만에 복귀하였다.길고 긴 공백기간(브론즈 4, 5만 품)을 지나고, 12년간 달려왔던 입시의 길도 이제 모두 마무리되었다. 대학 발표만을 기다리고 있는 상황이다.입시에 전념하느라 PS를 그만두는 동안 정말 많은 일이 있었다.일단 코딩 실력이 너무 많이 줄어들었다.전성기때 NYPC 2라운드를 합격해놓고, 본선에서 망쳤다. (간단한 실수 하나를 못봐서 자존심 상해서 그냥 4시간동안 그문제만 들이팠다. 근데 1~2달 쉬었다고 그렇게 못 할 일인가...?) 어쨌든 이제 입시가 끝났고, 학교에서는 모두가 고등학교의 마지막 시절을 만끽하는 중이다.나는 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..