BOJ
-
[17141] 연구소 2BOJ 2022. 1. 9. 13:01
https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 바이러스를 놓은 시점부터 생각해보면, 단순한 level-based bfs를 돌려주면 된다. 정확한 명칭은 모르겠는데, turn이 바뀌는 시점을 일일히 bfs 안에서 체크할 필요가 없이, bfs에서 사용하던 while(!q.empty())안에 sz=q.size(), while(sz--)를 한번 더 중첩하여 간단하게 구현할 수 있다. 바이러스를 놓는 경우의 수는 최악의 경우에 10C5정도, V+E도 3000을..
-
[2116] 주사위 쌓기BOJ 2022. 1. 9. 12:55
https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 맨 아래가 정해지면 그 위 n-1개의 주사위의 순서는 필연이므로 dfs 하듯이 구현해줄 수 있다. 간단하게 생각해서, 한쪽면에 올 숫자는, 위아래와 맞닿는 면 2개를 제외한 4개중의 최대값을 선택한다. 주사위의 맞은편의 연결된 인덱스(?)가 조금 헷갈리는데, 한번에 base[]={5, 3, 4, 1, 2, 0};처럼 상수마냥 정의해두면 그나마 조금 덜 헷갈린다. 이제는 맨 아래를 놓는 경우의 수를 찾으..
-
[21740] 도도의 수학놀이BOJ 2022. 1. 8. 16:20
https://www.acmicpc.net/problem/21740 21740번: 도도의 수학놀이 길이가 N인 수열이 주어진다. 도도는 이 수열의 수를 이어붙여 180도 회전시켰을 때 가장 큰 수를 만들려고 한다. 각 숫자를 180도 회전시켰을 때 환원되는 숫자는 다음과 같다. $0$ -> $0$ $1$ -> $1$ $2$ www.acmicpc.net 정렬의 기준은 "[16496] 큰 수 만들기"와 마찬가지로 string의 '+'와 부등호를 통한 사전순 비교로 간단히 구현된다. 해당 문제와 달리, 180도 회전하는 부분에 대한 처리와 하나의 수를 추가 할 수 있다는 조건이 추가되었고, 회전에 대한 처리는 간단히 정렬 전과 후에 한번씩 돌려줄 수 있다. 추가할 수는 가장 길이(자리수)가 길면서, 가장 큰 ..
-
[21608] 상어 초등학교BOJ 2022. 1. 5. 14:37
https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 그냥 잘 구현하면 되는 문제라 별로 적을게 없다.. 모든 (y, x)에 대해 (인접한 칸에 좋아하는 학생 수)를 구해야 하는데, 현재 (i, j)에서의 값을 cnt에 넣었고 현재 시점까지의 최대 cnt를 curScore에 저장해두었다고 생각해보면, cntcurScore인 경우에는 기존 모든 후보지를 clear()해주고 현재 위치를 추가하면 된다. 위 3가지 경우를 잘 나누어 주는게 이 ..
-
[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..