본문 바로가기

Problem Solving/BOJ 백준

 (132)
[ BOJ 백준 2163번 - 초콜릿 자르기 ] 해설 및 코드 https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 목적 쪼개는 횟수를 최소로하여 1x1 크기로 쪼갠다. 접근법 1. 가로로 먼저 쪼개든, 세로로 먼저 쪼개든, 쪼갠 개수에 쪼개진 조각..
[ BOJ 백준 2823 번 - 유턴 싫어 ] 해설 및 코드 https://www.acmicpc.net/problem/2823 2823번: 유턴 싫어 문제 상근이는 여자친구와의 드라이브를 위해서 운전을 배우고 있다. 도로 연수를 10년쯤 하다 보니 운전은 그럭저럭 잘하게 되었다. 하지만, 그는 유턴을 하지 못한다. 10년동안 도로 연수를 받았지만 유턴을 하지 못한다. 밥먹고 유턴만 연습했지만, 결국 유턴은 하지 못했다. 상근이는 유턴을 연습하기 위해서 시간을 투자하는 대신에 유턴을 할 필요가 없고, 유턴이 금지된 마을로 이사가려고 한다. 상근이가 이사가려고 하는 마을은 막다른 길이 있으면 안 된다. 막 www.acmicpc.net 목적 막다른 길이 있는지 없는지 확인한다. 접근법 1. 모든 길을 방문하여 막다른 길이 있는지 없는지 검사한다. 2. 막다른 길이 아니..
[ BOJ 백준 2629번 - 양팔저울 ] 해설 및 코드 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 www.acmicpc.net 목적 주어진 추 N개를 이용하여 측정할 수 있는 모든 무게를 구한다. 접근법 1. a[i]는 i 번째 추의 무게이고, s[i]는 1~i번째..
[ BOJ 백준 3109번 - 빵집 ] 해설 및 코드 https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 목적 건물('x')을 피해서 파이프를 겹치지 않게 놓을 수 있는 최대 개수를 구한다. 접근법 1. 파이프의 최대 개수는 R이하의 값으로, d..
[ BOJ 백준 2339번 - 석판 자르기 ] 해설 및 코드 https://www.acmicpc.net/problem/2339 2339번: 석판 자르기 하나 이상의 불순물과 보석 결정체로 이루어진 석판을 여러 조각으로 나누어 가공해서, 보다 높은 가치를 얻을 수 있도록 만들려고 한다. 이때, 높은 가치의 석판을 만들기 위해서는 석판을 여러 조각으로 나누되, 각 조각에는 불순물이 없도록 해야하며, 보석 결정체도 단 하나씩만 포함하고 있어야 한다. 또한, 석판에서 불순물을 빼내기 위해서는 불순물을 포함하고 있는 지점을 중심으로 잘라야 되는데, 석판의 결 때문에 가로 또는 세로 방향으로만 석판을 자를 수 있다 www.acmicpc.net 목적 석판을 자를 수 있는 여러 조건을 만족하여, 석판을 자를 수 있는 모든 경우의 수를 구하라. 다음은 석판을 자르는 한 가지의 예..
[ BOJ 백준 11729번 - 하노이 탑 이동 순서 ] 해설 및 코드 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 목적 세 개의 장대를 이용하여 첫 번째 장대에서 세 번째로 모든 원판을 옮겨야 한다. 접근법 1. 재귀식을 세워보자. -..
[ BOJ 백준 1405번 - 미친 로봇 ] 해설 및 코드 https://www.acmicpc.net/problem/1405 백준 1405번 미친로봇 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다. www.acmicpc.net 목적 로봇의 이동경로가 단순(방문한 곳을 재방문 하지 않음)할 확률을 구하자. 접근법 1. 완전탐색 알고리즘으로,동서남북 네 방향으로 이동할 수 있는 모든 경우에 해당하는 확률의 합을 구한다. *주의 : cout.precision(10); 코드를 사용하여 문제 조건에 해당하는 오차 범위로 변..
[ BOJ 백준 17136번 - 색종이 붙이기 ] 해설 및 코드 백준 17136 - 색종이 붙이기 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.acmicpc.net 목적 1×1, 2×2, 3×3, 4×4, 5×5의 총 다섯 종류의 색종이를 이용하여, 10x10 크기의 종이에 1이 ..

티스토리툴바