하바나바나나

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 교육적인 슬라이딩 윈도우 문제입니다. 원형으로 돌면서 $k$짜리 길이의 초밥들을 관리해주면 됩니다. 초밥이 추가될 때마다 visited 값을 늘려주고 초밥이 제거될 때마다 visited 값을 줄여주면 쉽게 구현할 수 있습니다. 쿠폰의 경우, 현재 가지고 있는 초밥 중 $c$번 초밥이 있는지 확인해주면 됩니다. 아래는 코드입니다. #include #def..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트래킹을 사용해 풀 수 있는 문제입니다. n-queen 문제와 비슷하게 비숍을 하나씩 놓는다고 생각하고, 하나의 비숍이 놓일 때 그 대각선에 있는 칸들은 전부 갈 수 없다고 표시해주면 됩니다. 다만 나이브하게 백트래킹을 돌리면 시간초과를 받게 되고, 체스칸의 흰색 영역과 검정색 영역을 나눠서 (비숍은 한 색으로만 이동할 수 있으므로) 풀면 풀 수 있습니다. 이 아이디어를 생각하는 것이 어려웠습니다. 아래..

https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 파이썬의 정규표현식을 쓰면 간단하게 풀 수 있습니다. 이렇게 날먹해도 되는걸까요? 아래는 코드입니다. import re s = input() regex = re.compile('^((100+1+)|01)+$') m = regex.match(s) if m: print("SUBMARINE") else: print("NOISE")

https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 간단한 bfs로 풀 수 있는 문제입니다. state의 범위가 크기 때문에 배열이 아닌 set으로 메모이제이션을 해주면 됩니다. 상태가 그렇게 많지 않을 거라는 믿음을 가지고 짜서 맞았는데, 왜 되는지는 잘 모르겠습니다. 믿음을 가지는 게 생각보다 어려운 거 같습니다. +) cologne 님이 알려주셨습니다. 액션을 한 번 하면 둘 중에 한 물통은 비어..

https://www.acmicpc.net/problem/1691 1691번: 석판 첫 줄에는 대리석 원판의 크기를 나타내는 W(가로 길이), H(세로 길이)가 들어있다. 다음 줄에는 우리가 원하는 크기의 개수 N이 있고, 그다음 N줄에는 그 크기들이 역시 가로, 세로 순으로 들어있 www.acmicpc.net dp로 풀 수 있는 문제입니다. 석판은 가로나 세로 방향으로 완전히 잘라야 한다는 점을 생각하면, 석판을 자르는 것을 부분문제로 나눠서 생각할 수 있습니다. 왼쪽 위를 원하는 모양의 석판 중 하나로 채워주면 두 가지 경우가 생깁니다. 가로로 먼저 자르고 세로로 자르는 것과 세로로 먼저 자르고 가로로 자르는 것입니다. 각 경우마다 새로 생기는 석판은 두 개가 되고 해당 석판을 다시 자르는 것으로 생..

https://www.acmicpc.net/problem/5821 5821번: 쌀 창고 쌀 창고 이 경우에는 창고의 위치에 대한 여러 개의 최적 위치가 있다: 10 이상 14 이하의 어느 정수 위치에든지 쌀 창고를 둘 수 있다. 위의 그림은 최적 위치들 중의 하나를 보여준다. 이 경우 10 www.acmicpc.net 쌀 창고의 위치가 주어지고 쓸 수 있는 비용이 주어질 때 해당 비용 내에서 최대한 많은 쌀을 옮기는 문제입니다. https://www.acmicpc.net/problem/2375 2375번: 농구 골대 세우기 첫 줄에 농구를 좋아하는 마을의 개수인 n이 주어지고 다음 줄부터 xi, yi, pi와 같이 한 줄에 농구를 좋아하는 하나의 마을에 대한 정보가 주어진다. 두 마을의 위치가 같은 경우..

https://www.acmicpc.net/problem/2185 2185번: 직사각형의 합집합 첫째 줄에 직사각형의 개수 N이 주어진다. 다음 N개의 줄에는 각 사각형의 정보를 나타내는 네 정수 x1, y1, x2, y2가 주어진다. 이는 사각형의 대각선으로 마주 보는 두 꼭짓점의 좌표가 (x1, y1), (x2, www.acmicpc.net 풀이 쓰기 귀찮아서 shiftpsh 님에게 대신 써달라고 했습니다. 아래는 shiftpsh 님의 글입니다. 둘레를 구해야 한다는 점에서 생각해 보면 $x$축과 $y$축을 따로 생각해도 된다는 사실을 알 수 있습니다. 지금부터는 $x$축에 수직인 선분들만에 대해 설명해 보겠습니다. 직사각형의 양 끝 선분을 봅시다. 왼쪽 선분을 '선분이 추가되는 이벤트'로, 오른쪽을..

SCPC 2차 예선을 쳤습니다. 잘 친건 아니지만 작년보다는 높은 성적이어서 만족스럽습니다. 계속 조금씩 성적이 오르고 있으니 내년에는 본선에 갈 수도 있지 않을까요? 아님망고... 까먹기 전에 풀이를 간단하게 남겨봅니다. 1. 수열 연산 배열에 연속된 구간에 update 쿼리를 통해 값을 1 증가시킬 수 있고, 배열의 모든 수를 $k$ 이상으로 만드는 update 쿼리의 최소 횟수와 그 때의 최소 비용을 구하는 문제입니다. 이 때 쿼리의 비용은 연속된 구간의 길이입니다. 잘 생각해보면 update 쿼리의 최소 횟수는 $k$ - 배열의 최솟값이라는 것을 알 수 있습니다. 최솟값을 $k$로 만들어주기 위해서는 $k$ - 최솟값 만큼의 update 쿼리가 필요하고 해당 쿼리를 하는 과정에서 나머지 모든 수를..

https://www.acmicpc.net/problem/5502 5502번: 팰린드롬 팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 www.acmicpc.net 딱 보고 아 이거 이차원 dp네 라고 생각했는데 그 이후로 한 이틀간 못 풀었습니다... 은둔고수 님이 저에게 완성된 팰린드롬에서 뺀다고 생각해 보라고 힌트를 주셨는데, 그거 듣고 조금 고민하다가 풀었습니다. $dp(i, j)$는 $i$번째 문자와 $j$번째 문자가 같으면 $dp(i+1,j-1)$이고 다르면 $min(dp(i+1, j), dp(i, j-1)) + 1$이 됩니다. cologne 님이 처음에 원래 문자..

https://www.acmicpc.net/problem/8872 8872번: 빌라봉 첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. N: 빌라봉의 개수 M: 이미 존재하는 길들의 개수 L: 뱀이 새로 지어진 길을 통행하는데 걸리는 시간 (일 단위). A, B, www.acmicpc.net 설명이 조금 길지만 정리해보면 포레스트가 주어질 때, 정점들을 잘 이어 트리로 만들면서 트리의 지름이 가장 작게 하면 됩니다. 트리의 지름을 사용하는 문제를 오랜만에 봐서 새로웠습니다. 이 문제를 풀기 위해서는 그리디한 방법을 사용할 수 있습니다. 임의의 트리 두 개를 이을 때, 각 트리의 지름에 중간에 있는 중점끼리 이어주는 것이 새로 만들어지는 트리의 지름을 ..