전체 글
-
[3649] 로봇 프로젝트BOJ 2022. 3. 30. 02:09
https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net s를 front()에, e를 back()에 놓고 sx이면 e--, 그 외에는 s++이다. 도중에 v[s] + v[e] == x인 순간이 한번이라도 발생하면, 해당 s, e는 abs(e - s)가 최대라는 조건을 자연스레 만족한다. 물론 그러한 경우가 한번도 존재하지 않았다면, danger를 출력하면 된다. #include using namespace std; #ifdef ..
-
[2458] 키 순서BOJ 2022. 3. 29. 00:18
https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 현재 정점이 자신의 키가 몇번째인지를 알수 있는가는, 플로이드를 이용해서 dst를 구한 뒤 현재 정점을 제외한 모든 정점이, 현재 정점에서 다른 정점으로 도달 가능 하거나(dst[cur][i] < INF) 다른 정점에서 현재 정점으로 도달 가능해야 한다. (dst[i][cur] < INF) 아이디어는 골4치곤 좀 어려운 느낌이다. 플로이드 태그는 스탠다드 난이도가 없어서 난이도 매기기가 애매한듯 싶..
-
[9370] 미확인 도착지BOJ 2022. 3. 29. 00:10
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이는 크게 2가지가 가능한데, 구간을 잘라서 다익스트라를 그대로 여러번 돌리는 방법이 있고 그래프를 적절히 조작하여 "[1445] 일요일 아침의 데이트"처럼 푸는 방법이 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endi..
-
[1719] 택배BOJ 2022. 3. 29. 00:07
https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 플로이드+역추적 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; int n, m, a[201][201], path[201][201]; constexpr int INF =..
-
[1038] 감소하는 수BOJ 2022. 3. 26. 00:40
https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이가 꽤 다양하다. 10자리, 9자리만 하드코딩하고 브루트포스하는 방법, 한자리 수를 넣고 뒤에 하나씩 이어붙이며 bfs하는 방법, 2차원 dp, 백트래킹 등이 가능한것으로 보인다. #include #include #include using namespace std; int dp[12][12]; int f(unsigned long long n) { int a[15] = {0}; i..
-
[5637] 가장 긴 단어BOJ 2022. 3. 25. 15:43
https://www.acmicpc.net/problem/5637 5637번: 가장 긴 단어 단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만 이루어져 있다. 단어와 다른 문자(마침표, 숫자, 심볼, 등등등...)로 이루어진 글이 주어졌을 때, 가장 긴 단어를 구하는 프로그램을 작성하시오. Apple의 www.acmicpc.net getchar()로 한글자씩 읽어서 파싱한 뒤, ans가 비어있거나 length()가 더 큰 경우에만 새로 갱신한 뒤에, 소문자로 바꿔서 출력하면 된다. #include using namespace std; string ans; int main(void) { while (1) { string cur = ""; while (1) { char c = getchar(); bool ..
-
[19236] 청소년 상어BOJ 2022. 3. 23. 23:41
https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 8방향 테이터를 이용한 사칙연산 수준의 구현이지만, 여러가지 조건이 많고, 특히 어떤 자료구조를 잡을지가 문제다. 자료구조의 개수가 많을수록 업데이트를 빼먹는 등의 실수를 할 가능성이 높지만, 퍼포먼스 측면에서 어떨땐 더 유리할 수 있다. 단순히 {번호, 방향, 행, 열}을 vector로만 넣으면 한번 id를 기준으로 sort한 뒤에, 업데이트는 erase()만으로 가능하다. 다..
-
[2637] 장난감 조립BOJ 2022. 3. 23. 16:46
https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net "[1516] 게임 개발"과 비슷하게, 위상정렬 하면서 방문하게 되는 노드에 dp를 적용한다. 간선의 방향을 뒤집고, 항상 n부터 출발하도록 구현할 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #end..
-
[1613] 역사BOJ 2022. 3. 23. 00:06
https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 사이클이 없는 단방향 그래프이므로, i에서 j로 갈 수 있다면 i가 j보다 먼저 일어난 사건이다. 간선의 가중치를 1로잡고 연결해서, 플로이드를 돌리면 쿼리당 O(1)에 가능하다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #en..
-
[14567] 선수과목 (Prerequisite)BOJ 2022. 3. 22. 23:37
https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 위상정렬로 들어간 turn를 저장한다. turn은 멀티소스 bfs처럼 관리하는 느낌인데, 그냥 큐에 turn을 넣으면 편하다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; int n,..