선택은 나의 것

문제 BOJ 10836 : https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 접근 이 문제는 서브태스크 문제로 입력값 등의 제한에 따라 점수가 다르게 채점된다. 즉 제한이 까다로워질수록 문제를 좀 더 효율적으로 풀어야 한다는 뜻이다. 문제를 잘 보면 i = 0, j = 0인 열과 행만 계산해주면 나머지 값은 따로 계산해 주지 않아도 된다. 이유는 다음과 같다. 제일 첫 번째 열과 행의 애벌레가 성장하는 크기는 0, 1, ..

문제 BOJ 11967 : https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 접근 베시는 불이 켜진 방으로만 갈 수 있고 방에서 다른 방의 불을 켤 수 있다. 이를 BFS로 풀다 보면 문제가 생기는데 테스트 케이스를 예로 보면 (1, 1)에서 출발하여 (1, 2)와 (1, 3)의 불을 켤 수 있다. 다음으로 (1, 2)를 방문하고 (1, 3)을 방문한다. (1, 3)에서 (2, 1)의 불을 켠..

문제 BOJ number : https://www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 접근 시뮬레이션 문제이기 때문에 문제에서 주어지는 조건만 잘 유념해서 구현하면 무리 없이 해결 가능한 문제이다. 다만 문제에서 주어지는 세로축의 좌표가 위에서부터 아래의 순서로 번호를 매기는 일반적인 방식이 아닌 그림과 같이 아래에서부터 위로 번호를 매기는 방식이어서 입력을 받을 때 B(땅의 세로 크기) + 1 - x(입력값) 해주었다. 코드 #..

문제 BOJ number : https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 접근 문제를 잘 못 이해하기 쉬운 문제이다. 문제를 좀 더 쉽게 풀어서 이야기해보자면 일반적으로 소는 현재 위치에서 인접한 상, 하, 좌, 우로 이동할 수 있다. 하지만 그중에서 일부는 벽으로 막혀있어서 다리를 만들어서 다리로만 이동할 수 있다. 이때 다리의 개수는 R로 주어지며 입력은 다리로 이어지는 두 좌표를 준다. 즉, ..

문제 BOJ 16967 : https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 접근 H x W 크기의 배열 A를 X, Y만큼 움직여서 그 값을 더해 만든 배열 B가 있다. H, W, X, Y의 값과 배열 B가 주어졌을 때 원래의 배열 A를 구하는 문제이다. 위와 같이 그림을 그려보면 규칙이 보인다. 겹쳐지는 사각형이 처음으로 등장하는 좌표를 (i, j)라고 했을 때 배열 A에서의 이 위치의 원래 값과 좌표 (..

문제 BOJ 17780 : https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 접근 문제에 주어진 규칙에 따라 체스판 위의 말을 움직여 게임이 몇 턴 만에 종료되는지 알아내는 문제이다. 이런 문제를 시뮬레이션이라고 한다. 난이도가 높은 시뮬레이션 문제일수록 요구하는 조건이 까다롭기 때문에 처음 코드를 구상하는 과정에서부터 꼼꼼하게 조건을 살펴보는 것이 중요하다. 코드 #include #include using namespace std; int ma..

문제 BOJ 15591 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 접근 한 정점에서 다른 정점으로의 USADO값의 최솟값을 구하기 위해 모든 정점에서부터 BFS를 돌아준 뒤 입력받은 K값보다 크거나 같은 값을 USADO로 가지는 것을 세주어서 문제를 풀었다. 다만 다 풀고 나니 이 과정을 따로 나눌 필요 없이 BFS 한 번에 해결할 수 있도록 짰으면 메모리와 시간을 더 효율적으로 사용..

문제 BOJ 1874 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 스택(LIFO : 후입선출)으로 문제에서 주어지는 수열을 만들 수 있는지 확인하는 문제이다. 후입선출 구조란 말 그대로 늦게 들어온 자료가 가장 먼저 나가는 구조를 뜻한다. 양동이 모양을 생각하면 편할 것이다. 이러한 후입선출 구조를 생각해서 코드를 짜면 쉽게 해결할 수 있는 문제이다...

문제 BOJ 3865 : https://www.acmicpc.net/problem/3865 3865번: 학회원 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 학회의 수 n이 주어진다. n은 100을 넘지 않는 양의 정수이다. 다음 n개 줄에는 각 학회의 학회원 정보가 문제에서 www.acmicpc.net 접근 구하고자 하는 임의의 학회에 가입한 회원의 정보는 사람일 수도, 또 다른 학회일 수도 있다. 이때 가입한 회원이 사람이 아닌 또 다른 학회라면 그 학회에 포함되어있는 사람들의 명단을 가지고 와야 하기 때문에 DFS로 접근하게 되었다. 하지만 이 과정에서 똑같은 학회가 여러 번 불릴 수 있기 때문에 메모이제이션(memoization)을 통해 visit 처리를 하여 동일한..

문제 BOJ 13417 : https://www.acmicpc.net/problem/13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net 접근 알파벳이 적힌 카드가 n장이 있을 때 이 카드를 순서대로 뽑아서 내가 가진 알파벳 카드들의 왼쪽 혹은 오른쪽에 배치할 수 있다. 이렇게 배치했을 때 사전 순으로 가장 빠른 문자열을 출력해주는 문제이다. 따라서 뽑은 알파벳이 현재 내가 가진 문자열의 가장 앞의 알파벳보다 사전 순으로 빠르다면 문자열의 가장 앞에(왼쪽에), 아니라면 뒤에(오른쪽에) 배치해 주면 된다. ..