코딩테스트

[백준] 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원을 ..

[정올] 여객선 (Cruise)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=2720&sca=99 JUNGOL www.jungol.co.kr 문제부터 요약해보면, 용량이 정해진 배들에 무게를 가진 사람들을 태웁니다. 이 때, 사람들을 모두 태우고 출항하지 않고 남은 배들의 무게의 총합이 최대가 되도록 만드는 것이 목표입니다. 출력은 남은 배들의 무게 총합을 출력해야 합니다. 아이디어는 총 3가지 정도로 구성됩니다. 1. 배를 순열로 배치해서 태울수 있는 사람들을 모두 태워봅니다. (DFS) (순열로 생각해야 하는 이유는 1, 2를 타는것과 2, 1을 타는게 다를 수 있기 때문) 2. 이 때 사람을 태우는 과정은 prefix sum과 binary upper bound 찾기를 사용합니다...

[백준] 페그 솔리테어

https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 게임을 하게 되는데, 핀은 최대 8개까지 있고, 핀은 이웃한 핀을 건너뛸수 있고, 이렇게 건너 뛴 경우 뛰임 당한 핀은 사라집니다. 이런 문제에서 이야기한 게임을 진행한 후, 남은 핀의 갯수와 최소 이동횟수를 출력해야 합니다. 핀의 위치를 기록해두고, dfs를 이용하여 문제를 해결할 수 있습니다. 핀이 건너뛸 수 있는 경우를 생각해보면, 매 핀은 상하좌우 4방향을 탐색합니다. 만약 이웃한 곳에 핀이 있다면, 그 다음 공..

[백준] 스도쿠

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제부터 간단하게 요약하면, 빈칸이 있는 스도쿠 판이 주어지면, 해당하는 스도쿠 판을 채워서 출력해야 하는 것이 문제입니다. 네모난 박스 9칸과, 가로9줄, 세로 9줄을 기록하는 array를 만들어 dfs를 진행합니다. 이 때, 표의 0,0부터 9,9를 각각 0부터 80까지 매핑을 시켜서 나눗셈 연산과, 나머지 연산을 통해 몇번 박스에 속하는지 조금 더 빠르게 연산할 수 있도록 하였습니다. 자세한..

[백준] 매직 스타

https://www.acmicpc.net/problem/3967 3967번: 매직 스타 매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 1부터 12의 숫자가 각 줄의 합이 26이 되도록 올바르게 배정될 수 있도록 배정하여, 가장 사전순으로 빠른 경우를 출력해야 하는 것이 문제입니다. DFS를 이용하면 됩니다. 계속 모양을 순회하지 않도록 미리, 12개의 점의 좌표를 기록해두는 방식을 이용합니다. 추가적으로 가지치기를 위해, 각 줄에 0~5의 번호를 매겨서 각..