PS/공부
-
JOI 2017/2018 Spring Training Camp Day1 3번 - Tents 풀이PS/공부 2024. 1. 6. 20:25
[JOI 2017/2018 Spring Training Camp Day1 3번 - Tents]https://www.acmicpc.net/problem/17682 17682번: TentsLet us denote a tent with the entrance directed to east, west, south and north by the characters ’E’, ’W’, ’S’, ’N’, respectively. There are nine ways to put up some tents as illustrated below.www.acmicpc.net [Subtask 1] $1 \leq H \leq 300$, $1 \leq W \leq 300$ (48점)세제곱 풀이를 떠올려봅시다. 행과 열 둘 중 하나를..
-
JOI 2012/2013 Spring Training Camp Day1 4번 - JOI Poster 풀이PS/공부 2024. 1. 4. 18:05
[JOI 2012/2013 Spring Training Camp Day1 4번 - JOI Poster] https://www.acmicpc.net/problem/17745 17745번: JOI Poster K 理事長は国際情報オリンピック日本選手団を応援するポスターを 3 枚デザインしている．ポスターに はそれぞれ J,O,I の文字を 1 文字ずつ盛り込む予定である．早速文字 J と文字 I のポスタ www.acmicpc.net 가로가 $W$, 세로가 $H$인 직사각형 평면 위에 $N$개의 점이 주어집니다. 이때 서로 다른 점 4개를 골라 $A$, $B$, $C$, $D$라고 해봅시다. 점 $A$를 중심으로 하고 점 $B$를 지나는 원을 $O_1$, 점 $C$를 중심으로 하고 점 $D$를 지나는 원을 $O_2$라 합시다...
-
JOI 2015 3번 - JOI 公園 (JOI Park) 풀이PS/공부 2024. 1. 3. 18:12
[JOI 2015 3번 - JOI 公園 (JOI Park)]https://www.acmicpc.net/problem/10715 10715번: JOI 공원20XX년에 IOI나라에서 열리는 올림픽 준비의 일환으로 IOI나라에 있는 JOI공원을 정비하기로 했다. JOI공원에는 N개의 광장이 있고, 1부터 N까지 번호가 붙어 있다. 또, 공원에는 광장을 연결하는 M개www.acmicpc.net $X$를 결정하는 데 있어, 광장 $1$로부터 광장 $i(2 \leq i \leq N)$까지의 최소 거리가 중요하므로 이 최소 거리들을 먼저 구해봅시다. 문제의 제한이 $2 \leq N \leq 100 000$, $1 \leq M \leq 200 000$이기도 하고, 특정 정점에서 다른 모든 정점까지의 최소 거리를 모두 ..
-
JOI 2016 2번 - スタンプラリー ２ (Collecting Stamps 2) 풀이PS/공부 2024. 1. 2. 19:14
[JOI 2016 2번 - スタンプラリー ２ (Collecting Stamps 2)] (원문) https://www.acmicpc.net/problem/11986 11986번: スタンプラリー ２ (Collecting Stamps 2) JOI 商店街には大通りに沿って N 個の店があり，JOI 商店街の入口から出口に向かってそれぞれ 1, 2, . . . , N の番号が付けられている．JOI 商店街は一方通行で，入口から出口方向へしか移動す www.acmicpc.net (한국어 번역) https://oj.uz/problem/view/JOI16_ho_t2 문제 보기 - 스탬프 수집 (JOI16_ho_t2) :: oj.uz 문제 보기 - 스탬프 수집 (JOI16_ho_t2) oj.uz 우선 원래 문자열에서 JOI의 개수를 세어..
-
JOI 2015 2번 - ケーキの切り分け２ (Cake 2) 풀이PS/공부 2024. 1. 1. 19:47
[JOI 2015 2번 - ケーキの切り分け２ (Cake 2)] https://www.acmicpc.net/problem/10714 10714번: 케이크 자르기 2 JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 www.acmicpc.net JOI 군의 선택은 2가지로 나누어질 수 있는 데 반해, IOI 양의 선택은 1가지로 제한되기 때문에 문제가 조금 쉬워졌습니다. 다음과 같이 dp식을 정의해봅시다. $\textrm{dp[pos][left][right]}$ : 지금이 $\textrm{pos}$의 차례이고, $\textrm{left}$번째 케이크..
-
23.07.08 - 23.07.10 공부 (트라이)PS/공부 2023. 7. 15. 23:52
백준의 '단계별로 풀어보기' 41단계에서 등장하는 트라이(Trie) 파트를 공부했다. 개념, 구현은 바킹독 블로그를, 추천 문제는 단계별로 풀어보기 41단계와 바킹독 블로그(아래 링크 참고)를 참고했다. (아래 사용하는 chk 배열 등의 용어는 바킹독 블로그의 내용을 따름.) https://blog.encrypted.gg/1059 1. 백준 14725번 - 개미굴https://www.acmicpc.net/problem/14725 14725번: 개미굴첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정www.acmicpc.net트라이 기본 문제..라..
-
23.06.04 - 23.06.10 공부 (그래프 파트 3 : MST)PS/공부 2023. 6. 10. 18:37
이번 그래프 파트는 '최소 신장(스패닝) 트리'라 불리는 MST이다. 바킹독 MST 문제집은 다 풀어놓은 상태라 라이 블로그 추천 문제집을 활용하였다. https://www.acmicpc.net/workbook/view/5057 문제 수가 그렇게 많지 않은데 공부 기간이 저렇게 길게 적혀있는 이유는.. 9373번 덕분이다. 나머지 문제는 하루만에 다 풀었는데, 9373번은 없는 시간 쪼개가며 고민하다보니 조금 오래 걸렸다. (사실 그마저도 풀어내지 못해서 해설을 봤다 ㅠ) 1. 백준 1922번 - 네트워크 연결 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. w..
-
23.06.02 - 23.06.03 공부 (그래프 파트2 : 데이크스트라)PS/공부 2023. 6. 4. 13:04
이번 파트는 [데이크스트라 알고리즘]이다. 역시 바킹독 문제집을 이용했다. 이전에 풀어놓은 게 좀 있어서 저번 [플로이드 알고리즘] 때보다 문제 수는 적지만, 난이도 분포는 살짝 더 높다. https://www.acmicpc.net/workbook/view/10433 1. 백준 1854번 - K번째 최단경로 찾기https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에www.acmicpc.net사실 이 문제의 접근은 예전부터 알..