문제 링크https://www.acmicpc.net/problem/35154 문제지훈이는 PS라는 자료구조를 만들었다. 하지만 PS라는 이름의 특성상 ProblemSolving으로 오해받고는 한다.PS 자료구조는 문자 P를 저장하는 스택(Stack)으로, 다음 두 명령어를 사용한다.PP: 문자 P 하나를 PS 스택 맨 위에 push한다.P: PS 스택 맨 위의 문자 P 하나를 pop한다. 단, PS 스택이 비어 있을 때는 수행할 수 없다.지훈이는 명령어들을 공백 없이 이어 붙이면 P의 나열이 된다는 사실을 알았다. 문득, P가 N개 나열된 문자열이 주어졌을 때 이를 유효한 명령어로 해석하는 방법이 총 몇 가지나 될지 궁금해졌다.처음에 PS 스택이 비어 있을 때, N개의 P로 이루어진 문자열을 유효하게 해..

문제 링크https://www.acmicpc.net/problem/35328 문제Farmer John is looking at his cows in a magical field and wants to take pictures of subsets of his cows.The field can be seen as a N × N grid (1 ≤ N ≤ 500), with a single stationary cow at each location. Farmer John's camera is capable of taking a picture of any K × K square that is part of the field (1 ≤ K ≤ min(N, 25)).At all times, each cow has a b..

문제 링크https://www.acmicpc.net/problem/35293 문제 멘헤라가 된 wlgh7407은 마음의 안정을 찾기 위해 알코올을 섭취하여 목표 단위 취기에 도달하고자 한다. wlgh7407의 앞에는 용량이 동일한 네 가지 선택지가 놓여 있다. 선택지취기 변화량순하리 레몬진 9도+9 단위순하리 레몬진 7도+7 단위순하리 레몬진 4.5도+4.5 단위생수-2 단위 wlgh7407은 목표 취기 N에 도달하기 위해 마셔야 하는 전체 액체의 양을 최소화하고 싶어 한다. wlgh7407이 정확히 N 단위 취기에 도달할 수 있는 선택의 최소 횟수를 알아내는 프로그램을 작성하시오.초기 취기는 0이고, 취기는 음수가 될 수 없다. 입력첫 번째 줄에 목표 취기 N이 주어진다. N은 음이 아닌 실수이다. (..

문제 링크https://www.acmicpc.net/problem/35143 문제 2026. 누군가에게는 아무 의미가 없을 수 있지만, 고려대학교에게는 매우 특별한 수이다.고려대학교의 프로그래밍 경시대회 KCPC 2025의 개최일은 2026년 1월 17일이다. 준서는 대회가 개최된다는 사실이 기뻐 날짜를 뚫어져라 보다가 고려대학교의 2026년이 무언가 특별하다는 사실을 깨달았다.그렇다. 2026년은 고려대학교 개교 121주년인데, 121은 팰린드롬이고 sqrt(121) =11, 121^2=14641도 팰린드롬이다. 다음에 이런년도가 오려면 무려 10080년 뒤인 12106년이 되어야 한다. 여기서 팰린드롬이란 앞과 뒤 어느 방향으로 읽어도 똑같은 수를 의미한다. 준서는 이처럼 어떤 양의 정수가 팰린드롬이..

문제 링크https://www.acmicpc.net/problem/34995 문제토카는 일정 금액까지 현금 대신 사용할 수 있는 쿠폰을 사용하여 음식을 주문하려 한다.쿠폰에는 N자리 정수로 쿠폰의 금액이 적혀 있다. 하지만 쿠폰 금액의 일부 숫자는 가끔 얼룩이 묻어 얼마인지 알아볼 수 없어 토카는 얼룩이 묻은 부분의 숫자를 적당히 지어내기로 한다. 쿠폰의 각 금액은 1 이상 9 이하의 숫자로 이루어져 있으며, 토카가 지어낼 숫자도 1 이상 9 이하의 숫자여야 한다.토카가 지어낸 쿠폰의 금액이 음식의 가격보다 작으면 주문할 수 없다. 토카가 음식을 주문할 수 있도록 쿠폰을 어떻게 지어내야 할지 알아보자. 입력첫 번째 줄에 쿠폰에 적힌 금액의 자릿수 N (1 ≤ N ≤ 10^5)과 쿠폰에 적힌 금액을 나타내..

문제 링크https://www.acmicpc.net/problem/32945 문제급식 시간이 시작되었다!학생 N명이 한 줄로 서서 배식을 받고 급식실에 앉는다. 배식은 1분 만에 완료되고, 모든 학생은 배식이 완료되자마자 급식실 자리에 앉는다. 즉, 줄의 맨 앞에서 i (1 ≤ i ≤ N)번째에 위치한 학생은 급식 시간이 시작된 지 i분 만에 자리에 앉는다.또한 학생마다 밥을 먹는 데에 걸리는 시간이 정해져 있다. 어떤 학생이 A분에 자리에 앉았고, B분 동안 밥을 먹는다면, 그 학생은 급식 시간이 시작된 지 A분, A+1분, ..., A+B-1분이 지난 시점에는 앉아 있고, A+B분이 지난 시점에 자리에서 일어나 급식실을 떠난다.대곽이는 모든 학생과 친하기 때문에 자신이 원하는 순서대로 줄을 세울 수 ..

문제 링크https://www.acmicpc.net/problem/34987 문제대전대신고등학교 영양사 선생님은 오늘도 학생들을 위한 급식 메뉴를 만들고 있다. 급식 메뉴는 맛 수치와 영양 수치를 가지며 초기에 두 수치는 모두 0이다. 영양사 선생님은 마법의 주문이라는 특별한 능력이 있으며, 마법의 주문을 사용할 때마다 맛 수치 혹은 영양 수치를 1 증가시킬 수 있다. 마법의 주문은 최대 M번까지 사용할 수 있다.학생들은 각자 음식에 대한 취향이 있어 급식 메뉴가 취향에 맞을 때만 먹는다. 구체적으로 N명의 학생 중 i번째 학생은 맛 수치가 ai, 영양 수치가 bi 이상일 때만 급식을 먹는다.학생들의 까다로운 취향 때문에 영양사 선생님은 마법의 주문을 어떻게 사용할지 어려움을 겪고 있다. 영양사 선생님을..

문제 링크https://www.acmicpc.net/problem/31566 문제안녕하신가! 힘세고 강한 아침, 만일 내게 물어보면나는 영도 근성은 매일 아침 개발 문서를 읽으며 하루를 시작한다. 한국어 문서를 다 읽은 근성은 해외 문서를 읽기 시작했지만, 세상의 다양한 언어로 작성된 개발 문서를 보고 눈앞이 아득해지기 시작했다. 이를 본 영도는 근성을 도와주고자 N개 언어 간 번역을 일부 제공하는 '정영도 봇'(이하 봇)을 만들었다. 봇은 프로토타입이기에 특이한 번역 로직을 지니고 있다.각 언어는 1 이상 N 이하의 중복되지 않는 고유 번호를 가진다.봇은 일부 (A, B) 언어 쌍에 대한 데이터를 가지고 있다. 여기서 A와 B는 언어의 고유번호를 의미한다.변환은 어떤 언어로 이루어진 문구를 다른 언..

문제 링크https://www.acmicpc.net/problem/33894 문제어제 박지성 카페 다녀왔습니다. 박지성 카페가 열린 건 아니고요, 그냥 카페에서 박지성 생각했습니다.카페에 간 건 아니고요, 그냥 집에서 커피를 마셨습니다. 사실 커피도 안마셨습니다그냥 캡틴박인 상태입니다 박지성의 열렬한 팬인 종학이는 종종 자신이 박지성이라고 상상하곤 한다. 대한민국의 캡틴 박지성은, 언제나 그렇듯 자신을 향해 달려오는 수비수들을 피해 최대한 오래 드리블을 해야 한다.어이없겠지만 축구장을 N개의 정점과 서로 다른 두 정점을 잇는 N-1개의 양방향 간선으로 구성된 트리라고 생각해 보자. 정점은 1번부터 시작하며, i번째 간선은 정점 ai와 bi를 잇는 길이가 wi인 직선 구간이다. 이때, 모든 간선의 길이 ..

문제 링크https://www.acmicpc.net/problem/34951 문제우주에는 N개의 은하와 M개의 블랙홀이 존재한다. 각 은하와 블랙홀은 거리 비용을 가진 단방향 워프 게이트로 연결되어 있으며, 사이클을 이루지 않는다.우주에는 다음과 같은 시간-거리 개념이 존재한다.우주의 시간 T는 처음에 0이다.블랙홀은 각자 양의 정수 크기 S를 가진다.어떤 블랙홀에 처음 도착하는 즉시, 그 블랙홀의 크기 S만큼 우주의 시간이 지나 버린다.우주의 시간이 S만큼 흐르면, 모든 은하/블랙홀 간 거리는 중력에 의해 S만큼 가까워진다.두 천체를 잇는 워프 게이트의 길이는 두 천체 간의 거리와 같다.즉 우주의 시간이 T이고 처음 주어진 워프 게이트의 길이가 w일 때, 각 워프 게이트의 길이는 max(w - T, ..

문제 링크https://www.acmicpc.net/problem/34156 문제카사네 테토(重音テト)는 바게트를 좋아한다! 그래서 오늘도 바게트를 먹으려고 한다. 테토는 한 입에 바게트를 모두 삼킬 수 없어서, 바게트를 최소 한 번씩 잘라서 먹으려고 한다.바게트 N개가 수직선 위에 놓여 있고, 이 중 i(1 ≤ i ≤ N)번째 바게트는 [si, ei] 구간에 위치한다. 1 ≤ i ≤ N을 만족하는 모든 i, j에 대해 si = sj, ei = ej를 동시에 만족하는 경우는 없고, 바게트의 길이 ei − si는 2 이상이다. 바게트 A가 바게트 B에 포함된다는 것은 sB ≤ sA와 eA ≤ eB를 동시에 만족하는 경우를 말한다. 테토는 바게트 A가 바게트 B에 포함되었다고 판단하면, 포함된 바게트 A를..

문제 링크https://www.acmicpc.net/problem/34697 문제대전과학고등학교에는 비가 내릴 때 효율적인 배수를 위해 1부터 N까지 번호가 붙은 N개의 하수구가 설치되어 있다. i번째 하수구는 높이 hi를 가지고 있으며, 모든 하수구의 높이는 서로 다르다. 서로 다른 두 하수구를 연결하는 양방향 간선인 배수로가 0개 이상 존재한다. 임의의 두 하수구 사이에는 배수로가 최대 한 개만 존재한다.가끔 하수구가 막히면 하수구에 물이 고이기도 한다.물이 고이지 않는 하수구는 다음 조건 1. 또는 조건 2.를 만족하는 하수구라고 재귀적으로 정의한다.막히지 않은 하수구이다.자신과 하나의 배수로로 연결된 하수구 중에서 물이 고이지 않는 하수구이며 자신보다 높이가 작은 하수구가 존재한다.만약 어떤 하..

문제 링크https://www.acmicpc.net/problem/34730 문제삶은 수많은 사건들로 이루어져 있다.한 사건에서 다음 사건으로 이어지는 길은 곧 선택이다.그러나 모든 선택이 언제나 허락되는 것은 아니다. 선택은 특정한 순간(주기)에만 열리며, 기회는 기다려주지 않는다. 한 번 선택을 내리면, 그만큼의 시간은 반드시 흘러간다.당신은 시각 0, 출발 사건 S에서 삶을 시작한다.흐르는 시간 속에서 사건과 선택을 거듭하며, 목표 사건 T에 도달하려 한다. 당신이 도달할 수 있는 가장 빠른 순간은 언제일까?만약 어떤 선택을 해도 목표에 닿을 수 없다면, 그것은 인연이 닿지 않은 것이다.정점의 개수 N, 유향 간선의 개수 M이 주어진다. 간선 e = (u → v)는 이동 시간 c, 활성 주기 ϕ를..

문제 링크https://www.acmicpc.net/problem/34983 문제프로그래밍 문제를 열심히 풀던 대신이는 어느새 solved.ac 프로필에 표시되는 8대 태그 중 여섯 개의 태그 레이팅을 800 이상으로 만들었다. '균형의 지배자 - 골드' 뱃지를 받고 기뻐하던 대신이는 욕심이 생겼다. 이제는 '균형의 창조자 - 골드' 뱃지를 가지고 싶어진 것이다. 뱃지를 위해서는 구현 문제와 기하 문제를 풀어야 한다...대신이는 열심히 문제들을 검색하여 자신의 실력으로 풀 수 있는 구현 문제와 기하 문제를 모았다. 각 문제들은 대신이의 구현 태그 레이팅과 기하 태그 레이팅 둘 중 적어도 하나를 올려 준다. 모아놓고 보니 문제가 너무 많아서, 대신이는 가능한 한 적은 수의 문제를 풀어 효율적으로 뱃지를 ..

문제 링크https://www.acmicpc.net/problem/35030 문제Good Bye, BOJ 2025! 대회는 2025년을 마무리하며 2026년의 시작을 기념하는 알고리즘 문제해결 대회이다.다들 저마다의 이유로 2026년을 기대하고 있겠지만, 위대한 수학자 준겸이는 남들과 조금 다른 방식으로 기대하고 있는 것 같다. 준겸이에 의하면, 2026이라는 수는 아래의 네 가지 수가 모두 소수이기 때문에 2026년은 특별한 한 해가 될 것이라고 한다. 2026 + 1 = 2027 2 × 026 + 1 = 53 20 × 26 + 1 = 521 202 × 6 + 1 = 1213여러분은 이 이야기를 듣고, 다른 연도에 대해서도 준겸이가 말한 좋은 성질이 성립하는지가 궁금해졌다.10진법으로 표기된 양의 정..