문제 링크: https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 그리디 알고리즘 "XXXX"를 찾아서 모두 AAAA로 바꿔주고 그다음 "XX"를 찾아서 모두 "BB"로 바꿔주면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include using namespace std; string s; int main() { ios_base::sync_with_stdio(false); cin >> s; while (s.find("XXXX") != string::npos) { s.repl..

문제 링크: https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 구현 0. 어항 표현 N*N 배열을 만들고 N행을 어항의 맨 밑바닥으로 표현했습니다. 1. 물고기의 수가 가장 적은 어항에 물고기 한 마리 넣는다. 여러 개라면 모두에 한 마리씩 넣는다. N행에 있는 원소들을 모두 순회하면서 최솟값을 찾으면 됩니다. 최솟값이 여러 개인 물고기를 모두 찾기 위해서 vector에 저장했습니다. // 1. 물고기의 수가 가장 적은 어항에 물고기 한 마리 넣..

문제 링크: https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net BFS, 시뮬레이션 0. 입력 온도, 온풍기, 조사하는 칸을 각각 2차원 배열로 표현했습니다. int temperature[21][21]; int heater[21][21]; int inspection[21][21]; (a, b)와 (c, d) 사이에 벽이 있다는 것을 표현하기 위해서 다음과 같이 4차원 배열을 만들었습니다. bool wall[21][21][21][21]; //wall..

문제 링크: https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 시뮬레이션, 중복 순열, DFS 이 문제는 실수할 여지가 많았습니다. 저는 1번에서 5번을 순서대로 함수로 구현했습니다. 다음 함수 구현으로 넘어가기 전에 함수를 먼저 테스트하고 넘어갔습니다. 함수를 만들 때마다 테스트를 했던 방식이 실수를 줄이는 데 도움이 많이 되었던 것 같습니다. 0. 물고기, 상어, 냄새 표현하기 물고기는 격자에 여러 마리가 존..

문제 링크: https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 구현, 시뮬레이션, 자료구조, deque(덱) 문제에서 요구하는 것을 그대로 구현하면 되는데 몇 가지 주의할 점이 있습니다. 1. 가장 처음에 양분은 모든 칸에 5만큼 들어있다. 처음에 양분을 초기화할 때 5로 초기화해야 합니다. A[r][c]로 초기화하면 안 됩니다. 2. 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 이 요구사항을 구현할..

문제 링크: https://www.acmicpc.net/problem/7682 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net DFS, 순열, 백트랙킹 알고리즘 각 테스트 케이스에 대해서 해당 케이스가 가능한 틱택토 경우의 수인지 판단하는 방법은 9개의 위치에 토큰을 놓는 순열을 구하면 됩니다. 9개의 위치에 토큰을 놓는 순열을 구하면 경우의 수는 9! = 362880입니다 가능한 순열을 state[362880][3][3] 배열에 하나씩 저장하고 테스트 케이스가 이 배열 안에 존재하는 지만 판단..

문제 링크: https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 시뮬레이션, deque 컨베이어의 회전은 deque를 이용하면 쉽고, 효율적으로 회전하는 걸 구현할 수 있습니다. -> deque에 각 칸을 순서대로 넣고 회전시킬 때 맨 뒤에 있는 원소를 맨 앞으로 보내면 됩니다. 이제 문제에서 나온 조건을 그대로 구현하면 되는데 1. 로봇은 1 ~ N번 칸에만 있을 수 있고, N번 칸에 도착한 로봇은 없애버리면 됩니다. 2. ..

문제 링크: https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 시뮬레이션 다음 세대의 드래건 커브를 구하는 방법은 이전 세대의 드래곤 커브가 지나온 방향을 역순으로 시계 방향으로 90도 회전해서 끝점부터 다시 가면 됩니다. 시계 방향으로 90도 회전하는 방법은 아래와 같습니다. if(방향 값 d == 3) d = 0 else d++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..