전체 글
-
[16930] 달리기BOJ 2022. 1. 4. 06:55
https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 간단하게 생각하면 4NMK정도의 풀이를 떠올릴 수 있는데, N, M, K모두 1'000이라 불가능하다. 그래서 O(NMK)를 O(NM)정도로 줄여야하는데, 핵심은 방문처리를 bool이 아닌 int형으로 해주는것이다. 코드 자체는 얼핏보기에 O(NMK)인데, 32번라인의 if (vst[y][x] = 0 && x >= 0 && y > k; int i, j; for (i = 0; i a[i]..
-
[22354] 돌 가져가기BOJ 2022. 1. 4. 02:58
https://www.acmicpc.net/problem/22354 22354번: 돌 가져가기 처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다. www.acmicpc.net UCPC에 나온 문제라 증명까지 풀이 슬라이드에 잘 나와있다. (https://ucpc.me/assets/ucpc21-prelim-solutions.pdf) 동일한 색의 돌이 연속으로 있을 때에는, 그중 하나만 가져갈 수 있다는 것이 풀이를 떠올리기 위한 핵심이 된다. 연속한 것 중 하나만 가져갈 수 있다면 모든 경우는 WBWB...나 BWBW..처럼 번갈아 나오는 경우로 압축할 수 있는데, 양끝은 어..
-
[8892] 팰린드롬BOJ 2022. 1. 2. 06:32
https://www.acmicpc.net/problem/8892 8892번: 팰린드롬 팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다. 상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC www.acmicpc.net 원래 문자열과, 뒤집은 문자열이 같은경우 팰린드롬이다. std::reverse()로 뒤집힌 문자열을 간단하게 구할 수 있고, 원래 문자열은 string간의 '+'연산으로 구할 수 있다. 입력된 n개의 문자열에 대해서 2중 for를 돌며 i != j인 (i, j)에 대해 v[i] + v[j]가 팰린드롬인지를 판별해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13..
-
[5014] 스타트링크BOJ 2022. 1. 2. 03:42
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1..F개의 노드가 있을때, i번 노드는 i-d, i+u번 노드와 연결되어 있다고 모델링해줄 수 있다. 가중치가 전부 동일한 상황에서의 최단거리는 bfs로 구할 수 있겠다. 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 41 #include #include #..
-
[17070] 파이프 옮기기 1BOJ 2022. 1. 2. 03:35
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 하나의 상태는 파이프의 한쪽 끝 좌표 (y, x)와 방향으로 구성할 수 있다. 이를 bfs나 dp로 계산하면 되는데, 회전은 45도로만 가능하다는 부분에 유의할 필요가 있다. 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 #include using namespace std; int n,..
-
[1574] 룩 어택BOJ 2022. 1. 1. 04:44
https://www.acmicpc.net/problem/1574 1574번: 룩 어택 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼 www.acmicpc.net board[i][j]가 빈칸이 아니라면, 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 41 #include using n..
-
[18138] 리유나는 세일러복을 좋아해BOJ 2021. 12. 31. 18:03
https://www.acmicpc.net/problem/18138 18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비 www.acmicpc.net 집합의 원소의 개수 n, m과 n개의 집합 x, m개의 집합 y가 주어진다. 티셔츠와 카라를 합쳐서 세일러복을 만들 수 있다면 두 정점간 간선을 생성해준다. 이후 이분매칭을 돌려주어 최대 매칭 수를 구하면 된다. 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..
-
[1071] 소트BOJ 2021. 12. 31. 08:18
https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 결론적으로 nlogn에 풀렸는데, n이 50으로 엄청 작아서 의아하다. 백트래킹으로 풀리는지는 잘 모르겠다... n이 이 문제보다 큰 100이어도 가지치기를 통해 백트래킹이 돌아갔던 문제가 하나 있는데, "[6590] 덧셈 체인" 처럼 백트래킹이 될 것이란 확신을 갖기 쉽지 않다. 이 문제는 두가지가 풀이를 구상하는 데에 꽤나 큰 힌트가 되었다. 첫번째는 "사전 순으로 가장 앞서는.."의 조건이고..
-
[12904] A와 BBOJ 2021. 12. 30. 02:28
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net s->t는 어렵지만, t->s는 유일하다. t의 맨 뒤가 'A'인 경우와 'B'인 경우를 나누어, 문제에 설명된 연산을 반대로 구현하면 된다. t가 empty string이 되기 전에 s와 같아지면 s를 t로 만들 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using name..
-
[2628] 종이자르기BOJ 2021. 12. 29. 04:46
https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 선형 자료구조 2개를 만들어서, 각각 {0, n}과 {0, m}으로 초기화한다. 가로와 세로의 순서에 맞게 입력되는 점선 번호를 전부 넣어주고, 정렬한다. v[i+1]-v[i]의 최대값을 가로에서 한번, 세로에서 한번 찾아서 두 수를 곱해주면 된다. 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 #incl..