랄뚜기의 코딩일기

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ ..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 ..

https://www.acmicpc.net/problem/20947 20947번: 습격받은 도시 $N$개의 줄에 도시의 정보를 출력한다. 각 줄은 $N$개의 문자를 포함하며 $i$번째 줄 $j$번째 문자는 도시의 세로 $i$번째 가로 $j$번째 칸에 대한 정보이다. 빈칸일 경우 ., 건물일 경우 O, 건물 잔해 www.acmicpc.net 문제 극악무도한 테러리스트 주현이가 도시를 습격했다. 습격받은 도시는 세로 N$N$칸, 가로 N$N$칸으로 이뤄진 격자 모양이며, 각 칸은 빈칸이거나 건물이 존재한다. 주현이는 자신이 만든 수제 폭탄을 건물이 없는 곳에 설치한다. 폭탄은 터질 때 상하좌우 각 방향에 대해 충격파가 퍼져나가는데, 충격파가 닿은 건물은 파괴되어 건물 잔해가 된다. 충격파는 건물 또는 건물 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 처음에 bfs를 왼쪽, 위, 오른쪽, 아래 방향으로 우선 순위를 줘서 탐색하면 해결 될 줄 알았다. 하지만 이렇게 bfs를 구현할 경우 탐색 순서는 다음과 같다. 따라서 나는 우선순위 큐 stl을 이용하여 거리 > y값이 작은 좌표 > x값이 작은 좌표 순를 우선순위로 정렬한 다음 bfs를 이용하여 문제를 풀었다. 조심해야 할 점은 pop을 할 때 조건을 만족하는지 검사해야 한다는 것이다...

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 오늘도 어김없이 문제를 제대로 읽지 않아 시간을 버렸다. 답이 3 초과인 경우를 배제해줬어야 했는데... 잘 읽어야겠다 ㅋㅋ 답이 3 초과인 경우를 배제해줬더니 시간초과가 떴다. 재귀를 돌 때 중복되는 경우가 발생하여 idx를 인자로 줘서 경우의 수를 줄여주었다. #include #include #include #include #include #include #include #include #i..

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 처음에는 그냥 타자의 순서를 정하는 게 메인인 문제인 줄 알았는데, 그건 기본이고 야구의 득점 시스템을 구현하는 것이 메인이었다. 타자 순서는 그냥 재귀와 반복문을 통해서 구현하였다. 야구의 득점 시스템은 크기가 3인 base라는 bool 순열을 이용하여 base에 사람이 있는지 없는지를 나타내 구현하였다. 안타를 쳤을 경우를 구현하는 것이 어려웠다. 수학적으로 간단히 구현이 가능할 줄 알았는데 경우의..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 이 문제를 풀면서 가장 어려웠던 것은 현재 상태를 저장하는 이중배열을 만드는 것이었다. 함수가 호출 될 때마다, 이중포인터에 공간을 할당하여 이중배열을 만든 뒤 전에 있던 상태를 저장해 주었다. 그 외에 막혔던 부분은 2 2 4 0 0 일 경우 왼쪽으로 움직이면 4 4 0 0 0 이 되어야 하는데 8 0 0 0 0이 되게 구현을 해놓아서 check이라는 배열을 이용하여..

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 그래프 이론과 구현이 융합된 문제이다. 처음에 아무것도 일어나지 않아 조금 헷갈리는 문제이나 실버여서 그런지 쉽다. 터져야 되는 폭탄을 queue에 넣고 3초 뒤에 그 size만큼 반복문을 돌리며 폭탄이 설치된 칸과 인접한 네칸을 빈 칸처리 해주었다. #include #include #include using namespace std; int R,C,N; int dx[]={-1,1,0,0}; int dy[]={0,..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 구현문제인데 푸는데 너무 오래 걸렸다. 결국 모든 경우의 수를 다 따져야 하기 때문에 효율적으로 구현하기 보다는 빠르게 구현하는데 초점을 두어야 한다. 구현 문제는 결국 집중력 싸움이라는 것을 잊지말자 ㅎ #include #include using namespace std; int N,M,s; int map[8][8]; vector v; int res=100; void up_count(..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 큰 알고리즘은 없고 그냥 구현 문제이다. 구현 문제를 풀 때 주의할 점은 놓치는 경우의 수가 없는지를 꼭 확인해야 한다는 것이다. 이 문제를 풀면서 뱀의 방향 정보를 모두 입력한 후에 끝나지 않는 경우를 파악하지 못하여 찾는데 상당한 시간을 사용했다. 만약 방향 정보를 모두 입력한 후에도 뱀이 죽지 않았다면 맵의 최대 길이를 실행시간으로 주었다. #include #include using namespac..