코딩테스트

[정올] 폭탄돌리기 (VOLIM)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1925&sca=9060 JUNGOL www.jungol.co.kr 구현 문제입니다. 문제부터 간단하게 요약해보면, 폭탄을 가진 사람을 퀴즈를 풀게 되고, 맞출 경우엔 다음 사람에게, 틀리거나 패스하는 경우에는 다음 문제 또한 풀어야 합니다. 210초~211초 사이에 폭탄이 터지고, 처음 폭탄을 가진 사람, 퀴즈의 수, 각 퀴즈에서 의사결정을 하는데 걸린 시간이 주어질 때, 폭탄이 터질 때 폭탄을 가지고 있던 사람의 번호를 출력해야 합니다. 실제로 원형을 나머지를 구하는 형태로 돌게 하여, 구현하면 됩니다. 코드는 아래와 같습니다. #include using namespace std; #define MAXN..

[정올] 등산로 찾기

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=1111&sca=4070 JUNGOL www.jungol.co.kr bfs를 이용하는 문제입니다. 산이 있는데, 가장 외곽 둘레에서 출발하여 목적지 까지 도착해야 합니다. 이 때, 출발높이와 도착 높이에 따라 사용된 힘의 크기가 달라질 때, 가장 경제적으로 올라갈 때 드는 힘을 구해야 합니다. 총 두가지 정도 생각을 해 볼 수 있습니다. 1. 가장 외곽 둘레부터 출발하는 방식 2. 산의 정상에서 출바하는 방식 총 이렇게 두 지점을 출발 위치로 잡을 수 있습니다. 저의 경우 가장 외곽부터 출발하도록 하였는데, 이렇게 할 때도 외곽의 한 지점만 넣어주고 자동으로 확산될 수 있도록 가중치를 주는 더 나은 방식을 이..

[정올] 귀가

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=491&sca=4070 JUNGOL www.jungol.co.kr BFS를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 목장 - 목장, 목장- 헛간을 잇는 길들이 존재하고, 소가 있는 목장들도 있고, 소가 없는 목장들도 있습니다. 이 때, 헛간으로 가장 먼저 올 수 있는 소와 그 거리를 구해야 합니다. 실제로 문제를 한번 읽어보는 것을 추천합니다. 헛간으로 부터 bfs를 진행하면 됩니다. 이렇게 bfs를 하다 대문자, 즉 소가 있는 목장에 도착하면 중단하는 형태로 진행을 합니다. 이렇게 bfs를 전부 진행하게 되면, 헛간으로 부터 각각의 소들에게 도달하는 최단 시간이 기록이 될 것이기 때문입니다...

[백준] Roadblock

https://www.acmicpc.net/problem/5917 5917번: Roadblock Every morning, FJ wakes up and walks across the farm from his house to the barn. The farm is a collection of N fields (1

[백준] 자동차경주대회

https://www.acmicpc.net/problem/2651 2651번: 자동차경주대회 첫째 줄에는 정비를 받지 않고 갈 수 있는 최대 거리가 주어진다. 둘째 줄에는 정비소의 개수가 입력되는데 정비소 수는 100개 이하이다. 셋째 줄에는 인접한 정비소 사이의 거리가 차례로 주어 www.acmicpc.net BFS를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 출발지와 도착지 사이에 정비소들이 있고, 각 정비소들은 정비시간을 가집니다. 자동차는 한 정비당 갈 수 있는 거리가 정해져 있습니다. 이 때, 총 정비시간을 최소화 해서 도착지점에 도착 했을 때, 거친 정비소, 정비소 갯수, 걸린 시간을 출력해야 합니다. 매번 출발지가 있을 것입니다. 처음에는 출발위치에서 출발할 것이고, 이후에는 정..

[백준] 모래성

https://www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net BFS를 이용하는 문제입니다. 문제부터 간단하게 요약해보면, 모래성이 있고, 파도가 치는 상황이 주어집니다. 매 파도가 칠 때, 파도와 가로 세로 대각선으로 닿는 부분이 강도보다 크거나 같은 경우 무너지게 됩니다. 이 때, 총 몇번의 파도가 몰려오고 나서 모래성이 수렴하는지를 구해야 하는 문제입니다. queue에 파도를 넣어 bfs를 이용하면 됩니다. 이 때, 몇번 파..

[백준] 영역 구하기

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS를 이용한 floodfill 기본문제입니다. 우선 문제부터 간단하게 요약해보면, 모눈종이에 검정색 직사각형들이 그려져 흰 구역들이 분리가 되게 됩니다. 이 때, 분리되어 나누어지는 영역의 개수와, 각 영역의 넓이를 오름차순으로 정렬하여 출력하는 문제입니다. 모눈종이에 검정색 영역들을 먼저 모두 채웁니다. 다음으로 흰 영역에서 floodfill하여 영역의 크기를 계산해줍니다..

[백준] Puyo Puyo

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 구현, 시뮬레이션 문제입니다. 문제부터 간단하게 요약하면, 애니팡 같이 뿌요뿌요라는 게임이 있습니다. 이 게임에서는 뿌요들이 4개이상 모이면 폭발하는데 매번 터질수 있는 푸요들이 모두 터진후 뿌요들이 내려옵니다. 그리고 또 다시 터질 것이 있다면 상태가 변화하지 않을 때 까지 반복됩니다. 이 반복이 총 몇번 일어나는지를 계산해 주는 것을 구현해야 합니다. - 푸요의 폭발 ..