[ 백준 12761 ] 돌다리 (c/c++)
https://www.acmicpc.net/problem/12761 [ 문제 요약 ]현 위치에서 + 1, - 1, + A, - A, + B, - B, * A, * B 만큼 이동할 수 있고 N에서 M까지 가야할 때, 최소한의 이동 횟수를 출력한다. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 경우는 존재하지 않는다. [ 문제 풀이 ]1. BFS로 첫 위치에서 0 ~ 100,000 사이의 모든 갈 수 있는 곳으로 이동한다.2. 만약 이미 가 본적 있는 곳이라면 가지 않는다.3. 한 번 이동할 때마다 이동 횟수를 + 1을 한다. [ 소스 코드 ]#include using namespace std;int N, M, A, B, num, cnt;int visited[101010];void BFS(..
[ 백준 17123 ] 배열 놀이 (c/c++)
https://www.acmicpc.net/problem/17123 [ 문제 요약 ] (r1, c1, r2, c2, v)가 주어지는데, 이 연산은 (r1, c1)부터 (r2, c2)까지 사각형 영역에 속한 A[r, c]의 값을 v만큼 더하는 것일 때, N개의 정수로 표현된 각 행의 합과 열의 합을을 공백으로 구분하여 출력한다. [ 문제 풀이 ]1. 누적합을 이용해서 최대한 반복을 적게 해야 한다.2. (r1, c1, r2, c2, v)가 주어지면 diff[r1][c1] += v, diff[r1][c2 + 1] -= v, diff[r2 + 1][c1] -= v, diff[r2 + 1][c2 + 1] += v 를 통해 사각형 내부의 합이 증가하도록 한다.3. 연산 과정이 끝나면 배열의 수를 계산한다...
[ 백준 1261 ] 알고스팟 (c/c++)
https://www.acmicpc.net/problem/1261 [ 문제 요약 ]상하좌우로 움직일 수 있고, 벽을 부술 수 있으며 미로의 크기를 나타내는 가로 M, 세로 N이 주어질 때, (N, M)으로 이동하려면 벽을 부수어야 하는 최소값을 출력한다. [ 문제 풀이 ]1. BFS을 이용하여 최단 경로를 구한다.2. 만약 맵에서 1을 지나가게 된다면 벽을 부순 횟수를 1 더한다.3. 현재 위치에서 이전에 벽을 부순 횟수와 이전 값을 비교하여 더 작은 수를 저장한다. [ 소스 코드 ]#include using namespace std;int N, M;int arr[111][111], D[111][111];int dx[] = {0, 0, 1, -1};int dy[] = {1, -1, 0, 0};voi..
