전체 글
[백준] 마라톤 1
https://www.acmicpc.net/problem/10655 10655번: 마라톤 1 젖소 박승원은 2번째 혹은 3번째 체크포인트를 건너뛸 수 있는데, 여기서 두 번째 체크포인트를 건너뛸 경우 경로는 (0,0) -> (11,-1) -> (10,0) 이 되며 거리는 14이다. 박승원은 이것보다 더 짧게 달릴 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 출발지에서 도착지까지 체크포인트를 순서대로 거쳐서 가는데, 한 체크포인트를 건너뛰고 도착지로 갈 때, 최단 경로가 몇이 나오는지를 구해야 합니다. 각각의 체크포인트 사이의 구간을 구하고, 한 구간을 건너 뛰었을 때의 구간사이의 거리를 구해서 얼마나 줄어드는지를 계산해서 최대로 줄어드는 경우를 구하는 방식으로 계산하였습니다. 실제 구현..
[백준] 공주님의 정원
https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 우선 문제부터 간단하게 요약하면, 꽃들의 피고 지는 시간이 주어졌을 때, 문제에서 준 정원에 특정 시기동안 꽃이 최소 하나이상 피어있도록 하는 최소 꽃의 갯수를 구해야 하는 문제입니다. 피는 날짜를 기준으로 꽃들을 정렬해 놓고, 처음엔 피는 날짜가 3월 1일 보다 작거나 같은 꽃들에 대해 지는 날짜가 가장 긴 꽃을 골라주고, 이후엔 이전에 골랐던 꽃이 지는날 다음날에 대해 3월..
[백준] 경비원
https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 우선 문제부터 요약하면, 직사각형 모양의 땅의 가장 바깥 경계에 동근이가 근무를 서고, 경계에 상점들 또한 존재합니다. 동근이와 상점들 사이의 최단거리의 합을구해야 하는 문제입니다. 원탁모양이라고 생각해서, 좌상단을 0, 그리고 시계방향으로 0, 1, 2, 3 등으로 숫자가 매핑될 수 있도록 하였습니다. 그렇게 각각의 좌표들을 변환 시킨 후, 양 방향으로 이동하는 거리중 최솟값을 뽑아서 계속 더해주는 ..
[백준] Cow Beauty Pageant
https://www.acmicpc.net/problem/5925 5925번: Cow Beauty Pageant Hearing that the latest fashion trend was cows with three spots on their hides, Farmer John has purchased an entire herd of three-spot cows. Unfortunately, fashion trends tend to change quickly, and the most popular current fashion is cows with only one sp www.acmicpc.net 우선 문제부터 요약하면, 3개의 영역을 1개로 합치기 위해서 놓아야 하는 점들의 갯수의 최솟값을 구하는 문제입니..
[백준] 뱀
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약해보면, 뱀이 과일을 먹으면 성장하고, 뱀에게는 command로 특정 초(시간) 에서 방향을 전환하라는 명령어가 떨어집니다. 이 때, 주어진 명령대로 행동 하였을 때, 뱀은 언제 죽는지를 구해야 하는 문제입니다. 구현 문제인데, 조금의 아이디어는 뱀을 queue로 관리하여 문제를 조금 더 편하게 해결이 가능합니다. 실제로 grid를 만들어 길을 ' . ', 과..
[백준] 상범 빌딩
https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 우선 문제부터 간단하게 요약하면, 3차원 공간에서 최단 시간에 탈출한다면 몇초가 걸리는지, 혹은 탈출이 불가능 하다면 trapped되었다고 출력해야 하는 것이 목표입니다. 기본적인 bfs의 구성을 단지 3차원으로 확장한 것입니다. 실제 구현은 아래와 같습니다. #include #include #include using namespace std; #define MAX_SIZE (30) int ans; i..
[정올] 동전 자판기(下)
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&code=1183&sca=3050 JUNGOL www.jungol.co.kr 우선 문제부터 간단하게 요약하면, 철수가 가지고 있는 동전 중 최대 개수의 동전을 이용하여 자판기의 물건을 구입하는 방법을 출력해야 합니다. 얼핏 보면 그리디 같지만, 최대 개수의 동전을 써야하므로 그리디를 바로 적용하기가 어렵습니다. 조금 고민을 해보면, greedy알고리즘을 적용할 수 있습니다. 전체 동전의 총 금액 - 만들어야 하는 금액을 최소 동전의 갯수로 만들게 되면, 남은 동전의 수가 자판기 물건을 구입하는 최대 동전의 수입니다. 13 4 5 2 6 3 4 문제의 예시로 이야기를 해보면, 총 금액은 2679원이고, 13원을 ..