선택은 나의 것

문제 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..