전체 글
[정올] 여객선 (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의 번호를 매겨서 각..
[백준] Escaping the Farm
https://www.acmicpc.net/problem/5921 5921번: Escaping the Farm The cows have decided on a daring plan to escape from the clutches of Farmer John. They have managed to procure a small inflatable raft, and during the cover of night, a group of cows will board the raft and row across the river bordering the farm. The pla www.acmicpc.net 문제부터 간단하게 요약하면, 소들이 농장을 탈출하는데, 소들은 무게를 가집니다. 이 때, 소들은 바보라 소들의 무..
[백준] 참외밭
https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 문제부터 간단하게 요약하면, ㄱ자를 회전 시킨 모양의 밭이 주어지고, 임의의 한 꼭짓점에서 반시계 방향으로 둘레의 변의 길이들이 주어집니다. 이 때, 밭의 넓이를 통해 밭에서 자라는 참외의 수를 구하는 문제입니다. 단위 면적당 자라는 갯수가 주어지므로, 넓이만 구하면 됩니다. 물론 가장 긴변의 양옆 변을 통해 찾는등 다른 방법들도 많겠지만, 그냥 주어진 변들을 이웃한 것들 끼리 모두 곱해서 더하..
[정올] Uniqueness
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=413&sca=99 JUNGOL www.jungol.co.kr 문제부터 간단하게 설명하면, N개의 문자열이 주어졌을 때, 동일한 문자열이 존재하는지 판단하는 프로그램을 작성해야 합니다. 만약 전부 다른 문자열이라면, unique를 출력하고, 아닌 경우에는 중복되는 문자열들에 대해서 등장한 번째를 출력해야 합니다. 실제로 문제를 한번 읽어보는 것을 추천합니다. map등의 자료구조를 이용하면 간단하게 해결할 수 있습니다. 만약 사용하지 않는다면, 앞에서 부터 하나씩 보면서, used를 체킹하는 방식을 이용하면 됩니다. alice bob libe lie libe libe alice bob alice alice 위..
[백준] 연속부분최대곱
https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 우선 문제부터 간단하게 요약하면, N개의 실수들이 나열 되어 있으면, 곱이 최대가 되는 부분을 찾아 계산해야 하는 문제입니다. 하나씩 곱해나가면서 최댓값을 갱신합니다. 이 때, 만약 결과값이 1보다 작아지면 1로 다시 초기화 해주는 형태로 구현하면 됩니다. 실제 구현은 아래와 같습니다. #include #include #include using namespace std; int N; ..