코딩테스트

[백준] 회전초밥

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net https://life318.tistory.com/151 [백준] 회전초밥 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주 life318.tistory.c..

[백준] 회전초밥

https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 우선 문제부터 간단하게 요약하면, 회전 초밥 벨트에 초밥들이 놓여 있는데, 연속한 k개와 쿠폰의 초밥을 먹을 때, 초밥 종류가 가장 많아지게 먹는다면, 총 몇개의 초밥을 먹을 수 있는지를 구해야 하는 문제입니다. 이 문제의 경우, 접시의 수가 30,000개로 엄청 크지 않으므로, 1칸씩 window를 이동하며, 내부의 초밥 종류를 새로 계산하는 방식으로 해결..

[백준] 사다리 조작

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 사다리가 주어지는데, 이 사다리에 사다리를 3개까지 추가해서 각각의 사다리가 도착지점도 번호가 같도록 만드려 하는데, 필요한 사다리의 최소갯수를 구해야 하는 문제입니다. DFS를 이용해야 합니다. 로직은 아래와 같습니다. 1. 각 사다리를 놓을 수 있는 지점에 사다리를 하나씩 놓아본다.(중복된 경우의 수 안하도록 주의) 2. 만약 ..

[백준] 토마토

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net bfs를 활용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 상자안에 익은 토마토, 안익은 토마토, 빈칸이 존재합니다. 이 때, 매일 익은 토마토 옆에 있는 안익은 토마토가 익을 때, 모든 토마토가 익기 위한 일 수를 구해야 합니다. bfs를 이용하면 되는 간단한 문제입니다. bfs의 초기 queue에 1인 지점들의 좌표를 넣어줍니다. (익은 토마토의 좌표를 넣습니다.)..

[백준] 치킨 배달

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 조합을 이용한 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 도시에 치킨 집들과, 일반 가정집들이 있습니다. 이 때, 가정집에서 가장 가까운 치킨 집 까지의 택시거리를 치킨 거리라고 정의합니다. ps. 거리의 종류에 대한 포스팅도 흥미로운 주제가 될 것 같습니다... 언젠가 기회가 되면 포스팅해보는 것으로... 도시에서 치킨집들을 M개 만큼만 골라서 가정집들의 치킨거리의..

[백준] 서강그라운드

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 플로이드 워셜(Floyd-Warshall) 알고리즘을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 예은이가 특정한 지역에 내려서 거리 m이하로 도착할 수 있는 곳에서 아이템을 먹을 때, 먹을 수 있는 아이템의 최대 갯수를 return해야 합니다. 실제로 문제를 한번 읽어보는 것이 좋습니다. 우선 도시가 만약 1~5까지 있다고 생각해 봅시다. 이 때, 예은이가 먹을 수 있는 아이템을 각 도시별..

[백준] 미세먼지 안녕!

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 방에 미세먼지와 공기 청정기가 있고, 매 1초마다 두가지 과정이 진행됩니다. 1. 미세먼지의 확산 2. 공기청정기로 인한 공기 정화와 순환 이러한 과정이 T 초간 일어난 후 방안의 전체 미세먼지의 수를 출력해야 하는 문제입니다. 특별한 알고리즘이 사용되지 않고, 말 그대로 1,2의 과정을 정확하게 구현하면 됩니다. for loop 내부에 ste..

[백준] 숨바꼭질 2

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net bfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 0 5, 3, 8 2-> 3, 1, 4 6-> 7, 5, 12 각각 시간에 따라 bfs의 진행과정에서 등장하는 정보들을 적어 두었습니다. 시간이 0인 경우 3, 시간이 1인 경우에는 시간이 0일 때의 3으로 부터 유도되는 4,2,6이 등장하고, 이후의 과정들 또한 마찬가지 입니다. 이 때 3은 시..