BOJ
-
[18870] 좌표 압축BOJ 2022. 2. 3. 13:42
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표압축은 naive로 풀기 어려울때, 다른 알고리즘을 적용하기 좋게 전처리하는 느낌인듯 싶다. 값의 범위가 상당히 줄어듦에 이점이 있어 counting sort처럼 값의 개수등을 저장하는 선형 자료구조를 MLE에 대한 걱정없이 선언할 수 있으나 압축후에는 값간의 대소관계만이 남음에 유의해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 1..
-
[1238] 파티BOJ 2022. 2. 2. 10:45
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 처음에 주어지는 X에 대한 다익스트라의 결과값을 미리 base[]에 저장해두고 i=[1, n] 에 대해 dst[x]+base[i]의 최대값을 구하면된다. 역추적이 없으니 보다 구현이 간단하지만, 다익스트라의 시간복잡도에 대한 이해, 다익스트라가 구하는것의 의미를 잘 알아야 풀 수 있는 문제인것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..
-
[12605] 단어순서 뒤집기BOJ 2022. 1. 29. 07:35
https://www.acmicpc.net/problem/12605 12605번: 단어순서 뒤집기 스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 www.acmicpc.net 한줄입력은 getline(), 공백기준 파싱을 string stream으로 해준다. cin.ignore()을 해주어야 getline()이 첫줄부터 제대로 받아온다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int T; vector v; int main(void) { ios..
-
[10422] 괄호BOJ 2022. 1. 29. 07:05
https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net dp를 채우는 방식이 독특한 문제, 홀수일 때에는 불가능하니 짝수일 때만 고려해주면 된다. 카탈란 수와 관련 있는 문제다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; using ll = long long; const ll M = 1e9 + 7; ll t, n, d..
-
[2216] 문자열과 점수BOJ 2022. 1. 29. 06:57
https://www.acmicpc.net/problem/2216 2216번: 문자열과 점수 첫째 줄에 세 정수 A, B, C (0 < A ≤ 10,000, -10,000 ≤ B, C < 0) 가 주어진다. 그리고 둘째 줄에 X가, 셋째 줄에 Y가 주어진다. 각 문자열의 길이는 3,000자를 넘지 않으며 빈 문자열은 입력으로 주어지지 www.acmicpc.net dp(i, j) : x[0, i), y[0, j)까지 사용했을때의 최적해로 놓고, x[i]==x[j]인 경우와 그 반대로 분기하면 되는데, 기저사례를 만드는 부분에 유의해야 한다. 0이나 -1따위를 return하는것이 아니라 한쪽을 이미 다 써버린 경우에는 (반대쪽 문자+공백)의 조합만 가능하므로 b를 남는 횟수만큼 곱해서 return해준다. 1..
-
[1505] 불 켜기BOJ 2022. 1. 26. 08:00
https://www.acmicpc.net/problem/1505 1505번: 불 켜기 세준이는 N×M 크기의 보드를 가지고 있고, 보드는 1×1 크기의 칸으로 나누어져 있다. 각 칸에는 전구가 하나씩 있다. 전구를 한번 만지면 전구의 상태가 반전된다. 즉, 켜있는 전구를 만지면 불이 www.acmicpc.net 첫 행, 첫 열을 브루트포스하게 선택한 뒤, (1, 1)부터 (n-1, m-1)까지 순차적으로 훑으며 (i-1, j-1)이 꺼져있을 때 (i, j)를 켠다는 그리디적 방식으로 완전탐색이 가능하다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4..
-
[16935] 배열 돌리기 3BOJ 2022. 1. 26. 03:50
https://www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 상하반전은 생각보다 쉬워서 잘 안나오는것 같기도 하지만, 2차원 배열을 회전하는건 종종 나온다. 매번 2차원 배열을 복사해두면 상대적으로 간단하게 구현이 가능하다. 1~4번은 그래도 자주 나올법한 구현이라 그대로 구현했지만, 6번연산처럼 한쪽만 구현하고 반대쪽을 3번 호출하는 방법도 있다. 1 2 3 4 5 6 7 8 9..
-
[4375] 1BOJ 2022. 1. 26. 02:40
https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 브루트포스하게, 매번 string에 '1'을 붙인다. int범위를 넘지 않도록 중간중간에 n으로 나눠주고, 값이 0이 되었다면 '1'을 추가한 횟수가 답이된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; int n; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); while (1) {..
-
[17471] 게리맨더링BOJ 2022. 1. 25. 09:22
https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net for(int bt=0; bt a[i]; for (i = 0; i > S; for (j = 0; j > x; x--; adj[i].push_back(x); adj[x].push_back(i); } } int S = (1
-
[1113] 수영장 만들기BOJ 2022. 1. 23. 09:31
https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 뭔가 특이하고 복잡한 문제인거 같지만, H=벽의 높이일때 O(HNM)으로 풀리는 문제다. 풀이의 방향을 잘 잡으면 정말 쉽게풀 수 있지만, 그렇지 않으면 한참을 헤메기 좋은 문제인듯 싶다. 물을 한칸씩 채워넣는다고 생각할때, bfs에서 가장자리(첫행or첫열or마지막행or마지막열)를 방문하면 그곳에는 물이 쌓일 수 없다. 만약 그러한 경우가 발생하지 않았다면, 기존에 방문한 ..