본문 바로가기

백준

 (14)
[Baekjoon] 18111 - 마인크래프트 (C++) https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를 www.acmicpc.net 블록을 설치하거나 제거해서 땅을 평평하게 만들어 줘야 합니다. 블록을 설치할 때는 1초, 제거할 때는 2초가 걸립니다. 땅의 크기..
[Baekjoon] 1966 - 프린터 큐 (C++) https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 www.acmicpc.net 중요도가 높은 문서를 먼저 뽑고, 중요도가 낮은 문서는 맨 뒤로 밀려나는 상황에 특정 문서가 몇 번째로 인쇄되는지 구하는 문제입니다. ..
[Baekjoon] 11866 - 요세푸스 문제 0 (C++) https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 처음엔 문제 이해가 잘 안 갔는데 그냥 처음부터 K번째 사람을 제거하고 다시 그 위치에서 K번째 사람을 제거하고... 계속 반복만 하면 되는 것 같더라고요. 중간의 데이터를 제거해야 하는 상황이라 자료구조 중 하나인 연결 리스트(linked list)를 사용하면 될 것 같다는 생각이 들었습니다. 연결 리스트는 C++에서 STL로 제공하는 list를 사용했습니다. 데이터 제거와 연결 리스트의 끝으로 이동하면 다시 처음으로 되돌리는 부분은 반복자(iterator)를 이용해 쉽게 구현할..
[Baekjoon] 1018 - 체스판 다시 칠하기 (C++) https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net M × N 크기의 보드가 주어집니다. 이를 8 × 8 크기의 정사각형으로 잘라서 색을 칠했을 때 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제입니다. 입력으로 들어오는 N과 M의 크기가 최대 50인 것을 보고 브루트 포스로 모든 경우의 수를 다 고려해서 풀면 될 것 같다는 생각이 들었습니다. 8 × 8 크기로 자른 보드에서 첫 번째 칸의 색이 하얀색인 경우와 검은색인 경우에 대해 개..
[Baekjoon] 9935 - 문자열 폭발 (C++) https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 www.acmicpc.net 문자열에서 특정 문자열(폭발 문자열)을 찾아 아예 없어질 때까지 반복해서 지워주는 문제입니다. 하지만 단순히 반복만 하면서 지울 경우..
[Baekjoon] 2156 - 포도주 시식 (C++) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 꽤나 고민했던 문제였습니다. DP(dynamic programming)로 풀어야 한다는 것은 알겠는데, 어떻게 접근을 해야 할지 잘 ..
[Baekjoon] 2178 - 미로 탐색 (C++) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS(breadth-first search)를 이용해 가장 짧은 거리를 구할 수 있는지 묻는 문제입니다. 한 번 나아갈 때마다 한 칸씩 나아갈 수 있으므로 가중치가 모두 1인 그래프에서 탐색하는 문제로 볼 수 있습니다. 가중치가 1이기 때문에 간단히 BFS를 이용해서 최단 거리를 구할 수 있죠. BFS 알고리즘을 구현할 수 있으면 크게 어려운 문제는 아닙니다. #include #include #include using name..
[Baekjoon] 7453 - 합이 0인 네 정수 (C#) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 예제 입력 1 복 www.acmicpc.net 단순히 모든 경우의 수를 고려해서 풀어도 문제는 없으나 \( O(n^4) \) 시간 복잡도가 나오게 되고, 입력으로 들어오는 ..

티스토리툴바