개발기록 개발기록

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 백트래킹 문제입니다. 백트래킹의 골격이 뭔지 알 수 있는 문제였던 것 같습니다. #include #include using namespace std; ..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를 www.acmicpc.net 직접 세보기 전까지는 답을 알 수 없는 완전탐색(?) 문제입니다. 저는 높이를 기준으로 위, 아래 블록의 수를 따로 빼서 작업을 ..

https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다. 즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다. (i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다. (i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다. www.acmicpc.net 단순 구현문제입니다. 문제에 나와있는 대로 구현하면 됩니다. method1은 틀렸는데 왜 틀렸는지 모르겠습니다.. #includ..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 조합, 시뮬레이션 문제입니다. 궁수의 위치를 조합으로 결정한 후, 각각에 대하여 시뮬레이션을 돌리고 최댓값을 찾습니다. 적 탐색은 bfs로 하였습니다. 탐색순서를 문제의 조건에 나온 순으로 합니다. 그리고 적을 만나면 저장해주고 탐색을 끝냅니다. /* (아기상어 문제의 경우 이렇게만 하면 틀립니다. = m) continue; if (visit[ty][tx] == 1) continue; q.push({ ty,..

https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 www.acmicpc.net 조금 특이한 bfs문제 입니다. 벽이 있는 곳으로 이동할 수 없고, 벽이 없는 곳으로 이동했다고 하더라도 내가 이동한 후에..

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 시간 개념, 라운드 개념이 저에겐 어렵습니다. 항상 두루뭉실하게 생각하는 습관 때문인거 같습니다. 그래서 각 시간마다 명확하게 무엇을 하는지 알 필요가 있다고 생각했습니다. 종이에 써보면 결국 2초 이상에서는 짝수에는 폭설, 홀수에는 3초 전의 폭탄이 폭발이 일어나는 것을 확인할 수 있었습니다. 그리고 폭탄은 '동시에' 터지는 개념이기 때문에 구현에 유의하여야 합니다. #include #include #includ..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 시작점과 도착점을 달리 하며 전부 탐색해봐야 되는 문제입니다 #include #include #include using namespace st..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net bfs 탐색으로 시뮬레이션 하는 문제입니다. 조건을 만족하면 탐색을 계속하고 아니면 종료해야합니다. 연합인 나라를 모두 알아낸 후에서..