PS/공부
-
JOI 2010/2011 2번 - 古本屋 (Books) 풀이PS/공부 2024. 12. 7. 15:51
[JOI 2010/2011 2번 - 古本屋 (Books)]https://www.acmicpc.net/problem/5550(AC 코드 - https://github.com/MongHwa/Algorithm/blob/main/Baekjoon/Books.cpp) 책의 장르 $G_i$가 10 이하임을 이용하여 봅시다.$val[g]$ - 장르가 $g$인 책의 가격이 모인 배열 이라고 할 때, [예제 입력 1]의 배열은 다음과 같습니다. $val[1] = \{14\}$$val[2] = \{13, 14, 11\}$$val[3] = \{12, 16\}$ 이때 장르2의 책 하나를 골라 가격의 최댓값을 만든다면 14를 고르는 게 최적이고, 책 두 개를 고른다면 14와 13을 고르는 것이 최적입니다. 따라서 각 장르에 따..
-
USACO 2014 January Contest Gold 3번 - Ski Course Rating 풀이PS/공부 2024. 10. 2. 12:01
(24.10.07 - AC 코드 전체를 추가하였습니다.) https://www.acmicpc.net/problem/9877 백준 알고리즘 태그에는 병렬 이분 탐색도 함께 붙어있습니다만, 이 글에서는 단순 분리 집합(유니온 파인드) 풀이를 제시합니다. 문제에서는 그래프를 $M$개의 행, $N$개의 열로 표현하고 있습니다만, 여기서는 $N$개의 행, $M$개의 열을 가진 그래프로 바꿔 설명하겠습니다. 또, 맨 왼쪽 위를 $0$행 $0$열로, 맨 오른쪽 아래를 $N-1$행 $M-1$열로 나타내도록 하겠습니다.이때 그래프의 $i$행 $j$열의 원소를 $i*M+j$번 노드라고 표현하면, 이 노드는 $i*M+j-1$번 노드(현재 노드의 왼쪽 노드), $i*M+j+1$번 노드(현재 노드의 오른쪽 노드), $(i-1..
-
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트라이 기본 문제..라..