보단잉의 블로그

[BOJ/Gold 4] 백준 31804 Chance!(C++)

문제 링크https://www.acmicpc.net/problem/31804 문제자료구조 시험에서 우찬이는 a점을 받았고, 상훈이는 우찬이보다 높은 b점을 받았다. 우찬이는 상훈이보다 점수가 낮아서 화가 났지만, 공부를 하나도 하지 않아서 상훈이보다 시험을 잘 볼 수는 없다는 것을 알고 있었다. 하지만 우찬이는 최소한 동점을 받고 싶었기 때문에, 자신의 수를 바꾸는 마법을 배워서 다음 3가지 마법을 사용할 수 있게 되었다. 물 주기: 수에 물을 주면 수가 1 커진다.밥 주기: 수에 밥을 주면 수가 2배가 된다.chance!: 수에 chance!를 외치면 수가 10배가 된다.하지만 chance!를 외치면 목이 너무 아프기 때문에 우찬이는 chance! 마법을 최대 한 번만 사용할 수 있다. 그리고 마법을 ..

문제 링크 https://www.acmicpc.net/problem/14615 14615번: Defend the CTP!!! 첫 번째 줄에 N(3≤N≤100,000)과 M(1≤M≤1,000,000)이 주어진다. N은 CTP에 존재하는 도시의 개수를 의미하고 M은 CTP에 존재하는 튜브의 개수를 의미한다. 다음 M개의 줄에 걸쳐 X, Y(1≤X, Y≤N)가 주어지 www.acmicpc.net 문제 지금으로부터 527년이 지난 서기 2544년, 항성 간 이동이 가능해진 인류는 태양계가 아닌 새로운 보금자리를 찾아 기술의 집약체인 CTP(Cho Technology Planet, 초 기술 행성)를 건설한다. 인공지능이 관리하는 CTP 안에서는 자연재해도 전쟁도 없었으며 많은 사람이 행복을 누리며 살아나갔다. C..

문제 링크 https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 문제 부유한 집안의 상속자 상근이네 집은 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 상근이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다. 위의 그림은 상공에서 본 상근이네 집의 건..

문제 링크 https://www.acmicpc.net/problem/31476 31476번: :blob_twintail_thinking: 첫째 줄에는 양갈래 굴의 방 중 가장 깊은 곳의 깊이 $D(1 \le D \le 12)$와 파손된 길목의 수 $N(0 \le N \le 2^D-2)$, 각 블롭 세력이 기본적으로 탐색하는 시간인 $U(1 \le U \le 100)$와 양갈래 블롭들이 갈라 www.acmicpc.net 문제 블롭들은 늘 새로움을 추구해 왔다. 이번에도 블롭들은 새로운 느낌을 원하였고, 이에 블롭들은 매일매일 하늘에 기도하게 된다. 이 기도를 들은 토카는 블롭들에게 양갈래 머리를 하사하였으며, 블롭들은 대 양갈래 시대를 맞게 된다. 그러나, 일부 블롭들은 거기서 더 새로운 헤어 스타일을 추..

문제 링크 https://www.acmicpc.net/problem/28333 28333번: 화이트 칼라 전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다. 오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 www.acmicpc.net 문제 전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다. 오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 검거하기 위한 작전을 세우고 있다. AdbyMe, Inc. 는 그가 현재 어느 도시에 있는지, 그리고 뮤직박스가 어느 도시에 있는지 파악했고, 그를 잡기 위해..

문제 링크 https://www.acmicpc.net/problem/29703 29703번: 펭귄의 하루 $1$ × $1$ 크기의 정사각형 칸으로 각각 나누어져 있는 $N$ × $M$의 행렬로 표현되는 펭귄 마을이 있다. 펭귄 마을의 정보는 문자 'S', 'H', 'E', 'D', 'F'로 나타난다. E는 천적이 없어 펭귄이 이동해도 괜 www.acmicpc.net 문제 1 × 1 크기의 정사각형 칸으로 각각 나누어져 있는 N × M의 행렬로 표현되는 펭귄 마을이 있다. 펭귄 마을의 정보는 문자 'S', 'H', 'E', 'D', 'F'로 나타난다. E는 천적이 없어 펭귄이 이동해도 괜찮은 안전 구역을 나타내며, D는 펭귄의 천적인 바다표범이 살고 있어 펭귄이 이동할 수 없는 위험 구역을 나타낸다. 그리..

문제 링크 https://www.acmicpc.net/problem/30702 30702번: 국기 색칠하기 세계의 여러 나라들은 자신의 나라를 상징하는 깃발인 국기가 있는데, 그중에는 색만 다르고 모양이 비슷한 국기들이 있다. 국기는 $N$행 $M$열의 격자판(행렬)으로 구성되어 있다. 격자판의 각 www.acmicpc.net 문제 세계의 여러 나라들은 자신의 나라를 상징하는 깃발인 국기가 있는데, 그중에는 색만 다르고 모양이 비슷한 국기들이 있다. 국기는 N행 M열의 격자판(행렬)으로 구성되어 있다. 격자판의 각 칸을 이루는 색은 A부터 Z까지의 영어 알파벳 대문자로 표현한다. A[i][j]를 국기 A의 i행 j열의 색이라고 하자. 두 국기 A, B 가 주어졌을 때, 모든 i, j(1 ≤ i ≤ N; ..

문제 링크 https://www.acmicpc.net/problem/30024 30024번: 옥수수밭 옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 $N$행 $M$열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 www.acmicpc.net 문제 옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 N행 M열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 옥수수의 가치를 측정해서 서로 다른 정수 1, 2, ⋯, N × M을 부여했다. 민석이는 처음에 옥수수밭 바깥에 위치한다. 민석이는 옥수수밭 바깥을 돌아다니면서 옥수수밭 바깥과 인접한 칸의 ..

문제 링크 https://www.acmicpc.net/problem/28280 28280번: 귀납법 각 테스트케이스마다 한 줄에, $1$에서 시작해서 $2$배를 하거나 $1$을 빼는 행동을 최소 몇 번 반복해야 $k$를 만들 수 있는지 출력한다. 만약 $k$를 만들지 못한다면, 대신 Wrong proof!를 출력한다. www.acmicpc.net 문제 입력 첫 줄에는 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 20) 각 테스트케이스마다 한 줄에 양의 정수 k가 주어진다. k의 총합은 4 × 10^6을 넘지 않는다. 출력 각 테스트케이스마다 한 줄에, 1에서 시작해서 2배를 하거나 1을 빼는 행동을 최소 몇 번 반복해야 k를 만들 수 있는지 출력한다. 만약 k를 만들지 못한다면, 대신 Wrong ..

문제 링크 https://www.acmicpc.net/problem/28256 28256번: 초콜릿 보관함 각 테스트 케이스마다, 화면의 표시가 올바르다면 1, 아니라면 0을 출력한다. www.acmicpc.net 문제 코코는 3 × 3의 사각 격자 모양의 초콜릿 보관함을 갖고 있다. 이 보관함은 가운데 칸이 막혀 있고 그 자리에 숫자를 표시하는 화면이 붙어 있다. 나머지 8칸에는 초콜릿을 최대 하나씩 보관할 수 있다. 화면에는 숫자가 최대 4개까지 표시되고, 각각의 숫자는 초콜릿이 들어있는 연결된 칸의 개수를 나타낸다. 숫자가 여러 개이면 오름차순으로 표시된다. 두 칸이 한 변을 따라 맞닿아 있으면 그 두 칸은 연결되어 있다고 한다. 코코는 똑같은 초콜릿 보관함을 하나 더 만들어서 한별이에게 선물하려고..

문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고,..

문제 링크 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 문제 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 구구의 집으로 들어가는 입구는 한 개이며 입구과 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다. 구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는..

문제 링크 https://www.acmicpc.net/problem/27978 문제 건덕이는 지난 보물찾기에서 보물을 찾는 데 성공했다. 이제는 배를 타고 세계 곳곳을 누비며 보물을 찾아 나서는 보물 탐사대가 되었다. 건덕이는 주변 섬들의 지형이 담긴 가로 W칸, 세로 H칸의 지도를 구했다. 지도에는 주변 바다의 지형이 나타나 있다. 바다와 암초로 이루어져 있는데, 배는 암초 위를 지나다닐 수 없다. 지도의 가장 왼쪽 위는 (1, 1), 오른쪽 아래는 (H, W)이다. 건덕이의 배는 매번 인접한 8칸 중 한 곳으로 이동할 수 있다. (r, c)와 인접한 칸은 max(|r − x|, |c − y|) = 1인 (x, y)이다. 안전한 항해를 위해 지도 바깥으로는 나가지 않는다. 바다의 물살이 지도 기준 왼쪽..

문제 링크 https://www.acmicpc.net/problem/25307 문제 시루는 부모님과 함께 백화점에 갔다. 부모님은 쇼핑할 것이 많기 때문에 여러 곳을 돌아다녀야 하고, 시루는 부모님과 함께 걸어다니는 것이 너무 힘들어서 의자에 앉아서 쉬려고 한다. 백화점은 세로 길이가 N, 가로 길이가 M인 격자 형태이고, 상하좌우로 인접한 칸으로 이동할 때마다 1 만큼의 체력을 소모한다. 시루는 현재 위치에서 출발해 백화점 곳곳에 있는 의자 중 하나를 찾아가서 앉으려고 한다. 시루는 백화점 밖으로 나가면 부모님께 혼나기 때문에 백화점 밖으로 나갈 수 없다. 백화점에는 건물을 지탱하기 위한 기둥과 옷을 전시하기 위한 마네킹이 있다. 시루는 기둥이 있는 칸으로 이동하지 못하고, 마네킹을 무서워하기 때문에 ..

문제 링크 https://www.acmicpc.net/problem/17394 17394번: 핑거 스냅 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼 www.acmicpc.net 문제 [어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼고 손가락을 튕기면, 사용자가 원하는 것을 할 수 있다. 그러나 반동이 매우 심하기 때문에 그리 많이는 사용할 수 없다. 정신 나간 수학자 Sonaht는 우연히 이 인피니티 건틀렛을 손에 넣게 된다. 그러..