이동식 저장소

코드포스에는 왜 이리 지루한 사람이 많은가? Problem - 455A - Codeforces codeforces.com 지문이 헷갈리기 쉽게 쓰여 있어서, 일단 문제를 정확히 이해하자. $n$개의 정수 $a_{1},~a_{2},~\cdots,~a_{n}$이 있다. 임의의 $a_{k}$를 골라 지우고, 모든 $a_{k}-1$과 $a_{k}+1$을 지운다. 예를 들어 $2$를 하나 지웠다면 모든 $1$과 $3$도 지워야 한다. 이때 얻을 수 있는 점수는 $a_{k}$점이다. 수를 하나 지우면 양 옆의 수도 없어져서 골치아픈 문제이다. 만약 $a_{k}-1$만 지워지는 조건이었다면 골드 하위 수준의 문제였을 것이다. 그러나 아주 간단한 제한을 걸면 이 문제 역시 골드 하위급으로 만들어버릴 수 있다. 바로 수..

Problem - 327A - Codeforces codeforces.com 0과 1로 이루어진 길이 $N$짜리 수열이 있다. 이 수열에서 연속된 구간 $[i,~j]$를 단 한 번만 골라 구간 안에 있는 모든 0을 1로, 1을 0으로 뒤집는다. 뒤집은 후에 1은 최대 몇 개 있을 수 있을까? 이 문제는 제한이 매우 작아서 $O(N^{3})$에도 풀 수 있지만, $N$이 커지더라도 풀 수 있는 방법을 생각해 보자. Maximum Subarray 먼저 Maximum subarray라는 개념을 알아야 한다. Maximum subaray는 배열의 끝 칸에서 끝나는 부분합 중 최댓값을 구하는 알고리즘이다. 식으로 쓰면 $ms[i]$는 $[1,~i]$ 구간에서 $i$를 포함하는 부분합 중 최댓값을 의미한다. 배열 ..

1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net 뭔가 많이 본 듯한 문제이다. 어디서 봤나 했더니 2568번 전깃줄 문제와 매우 유사하다. 물론 풀이가 유사하다는 건 아니고 그림이 비슷하다는 소리. 이 문제에서는 전깃줄이 교차하는 횟수를 세어야 한다. 문제에 두 전깃줄이 교차하는 조건이 주어져 있는데, 계산의 편의를 위해 왼쪽에 있는 정점을 오름차순으로 살펴보면서, 각 정점의 전깃줄이 다른 전깃줄과 몇 번 교차하는지 계산해 보자. 왼쪽 정점 $i$와 오른쪽 정점 $j$에 연결된 전깃줄을 $(i, ~..

지난 글에서 Java의 컴파일과 관련된 두 가지 옵션을 공부했다. sourceCompatibility vs. targetCompatibility App level ``build.gradle`` 파일에는 ``sourceCompatibility``와 ``targetCompatibility``라는 속성이 정의되어 있다. android { ... compileOptions { sourceCompatibility JavaVersion.VERSION_1_8 targetCompatibility JavaVersion.VERSION_1_8 } } 이 thinking-face.tistory.com 이번 글에서는 Kotlin의 ``jvmTarget`` 옵션에 대해 공부해 보자. jvmTarget android { ... k..

14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 블록 사이에 빗물이 얼마나 고이는지 구하는 문제이다. 2차원 공간의 바닥은 막혀 있다고 가정한다. 바닥이 막혀 있으므로 물이 빠져나갈 수 있는 방향은 왼쪽 또는 오른쪽이다. 설마 물이 위로 증발하지는 않을 것이고.. 그렇다면 블럭을 제외한 모든 빈 공간을 물로 채운 후, 왼쪽 또는 오른쪽으로 빠져나가는 물을 제외하면 된다. 2차원 공간에 다음과 같이 물을 채운다. 검은색은 블록이다. 왼쪽과 오른쪽으로 물이 얼마나 빠져나갈 수 있는지 시뮬레이션해 ..