본문 바로가기

Algorithm Problems

 (212)
[백준/C++] 14500번: 테트로미노 문제https://www.acmicpc.net/problem/14500문제 요약폴리노미노란 크기가 1 × 1인 정사각형을 여러 개 이어서 붙인 도형이고, 다음과 같은 조건을 만족해야한다. 1. 정사각형은 서로 겹치면 안 된다.2. 도형은 모두 연결되어 있어야 한다.3. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 그 중, 정사각형 4개를 이어 붙인 폴리오미노를 테트로미노라고 하고, 다음과 같은 5가지가 있다.  N × M 크기의 격자 종이에 테트로미노 하나를 놓으려고 할 때,테트로미노가 놓인 칸에 쓰인 수들의 합을 최대를 출력한다.코드#include #include using namespace std;int board[550][550];bool visited[..
[백준/C++] 로봇 청소기 문제https://www.acmicpc.net/problem/14503문제 요약로봇 청소기가 있는 방은 N × M 크기의 직사각형 좌표로 나타낼 수 있다. 방의 각 칸은 벽 또는 빈 칸이고, 청소기는 바라보는 방향(동, 서, 남, 북)이 있다. 로봇 청소기는 다음과 같이 작동한다. 1. 현재 칸이 아직 청소되지 않은 경우- 현재 칸을 청소한다. 2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면, 한 칸 후진하고 1번으로 돌아간다.- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면, 작동을 멈춘다. 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우- 반시계 방향으로 90도 회전한다.- 바라보는 방향을 기준으로 앞쪽 칸이..
[백준/C++] 9935번 문자열 폭발 문제https://www.acmicpc.net/problem/9935문제 요약문자열과 폭발 문자열이 주어진다. 문자열이 폭발 문자열을 포함하고 있다면, 해당 문자열을 사라지고 남은 문자열이 합쳐진다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있다면, 다시 해당 문자열은 사라진다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 모든 폭발이 끝난 후, 남아 있는 문자를 출력하고, 없다면 FRULA를 출력한다.코드#include #include #include using namespace std;string text, boom;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> text >> boo..
[백준/C++] 말이 되고픈 원숭이 문제https://www.acmicpc.net/problem/1600문제 요약N × M 크기의 격자판이 존재할 때, (0, 0)에서 (N - 1, M - 1)까지 이동하고자 한다. 2가지 방법으로 칸을 이동할 수 있다. 1. 상하좌우로 인접한 칸을 1번의 동작으로 움직일 수 있다.2. 체스에서의 나이트처럼 칸을 1번의 동작으로 움직일 수 있다. 이 때, 2번째 방법은 K번만 움직일 수 있고, 장애물이 있는 칸(1)으로는 이동할 수 없다. 시작지점에서 도착지점까지 갈 수 있는 최소한의 동작 횟수를 출력한다.코드#include #include #include #include using namespace std;int n, m, k;int board[220][220];// (0, 0)에서 (i, j)까지 말처..
[백준/C++] 2636번: 치즈 문제https://www.acmicpc.net/problem/2636문제 요약N × M 크기의 정사각형 칸들로 이루어진 사각형 판이 있다. 판의 가장 자리에는 치즈가 놓여 있지 않고, 각 칸에는 치즈가 놓여 있거나 공기가 있다. 공기에 맞닿은 치즈는 한 시간이 지나면 녹아 없어진다. 치즈가 모두 녹아서 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아 있는 치즈 개수를 출력한다.코드#include #include #include using namespace std;int n, m;int board[110][110];int temp[110][110];// visited[i][j] : (i, j)가 공기인지 여부bool visited[110][110];int dx[4] = { 0, 0, 1, -1 }..
[백준/C++] 13909번: 창문 닫기 문제https://www.acmicpc.net/problem/13909문제 요약N개의 창문이 있고, N명의 사람이 있다. 차례대로 1번부터 N번째 사람이 N의 배수 번째 창문을 열려 있으면 닫고, 닫혀 있으면 연다. 마지막으로 열려 있는 창문의 개수를 출력한다.코드#include using namespace std;int main() { int num; cin >> num; if (num 코드 설명과정이 잘 이해가 안가서 직접 손으로 그려보았다. 0이 2번, 4번, 6번, 8번 이런 식으로 반복되고, 1이 찍히는 것을 알 수 있어서 코드로 구현했다..고찰뭔가 이상해서 다시 봤더니, 1, 4, 9, 16, ... 제곱수에 해당하는 번호에 1이 찍힌다는 사실을 알게 되었다. ㅠㅠ

티스토리툴바