차가운오미자님의 유리병

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 일단 배양 접시의 크기를 주지 않았지만 최대 300번 시뮬을 돌릴 수 있고, 처음 주어지는 세포 범위의 크기가 50이라 했으며, 세포는 가장 생명력이 약한 친구(1)도 2번 동안은 살아있으므로 최대 150칸 뻗어나간다는 것을 알 수 있다. 그래서 넉넉하게 150 *2 + 50 + 여유분 --> 이 정도로 맵 사이즈를 지정하면 된다. 세포의 좌표, 생명력, 활성화 여부 등을 배열에 저장한다..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 아이디어 내기는 어렵지 않다. 어차피 최대 4번 벽돌 던질 수 있으니까 DFS로 벽돌 열 번호를 고르고 시뮬레이션을 돌려보면 된다. 나는 그나마 시간을 단축하기 위해서 모든 단계마다 시뮬을 돌려주었다. (벽돌 하나 던지고 다음 단계로 넘어가고 이런식으로, 그럼 같은 부수기 동작을 훨씬 덜 할 수 있다. 다 던지고서 시뮬레이션을 돌리지 말라는 뜻) 내가 헤맸던 건 별 것도 아닌 W가 가로고..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 이해 파랑 구슬과 빨강 구슬이 한꺼번에 움직이는 동작을 구현하는 게 어렵다. 최소 횟수를 구하는 거니까 BFS를 이용하면 되는데, 한 칸 움직이는 게 아니라 쏠리는 거라서 조금 까다로웠다. BFS() 일단 BFS부터 설명하자면 파란구슬의 좌표, 빨간 구슬의 좌표를 큐에 넣어준다. visited배열은 4차원으로 (파란 구슬 좌표 + 빨간 구슬 ..

https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 문제 이해 처음에 풀고 다 맞는데 왜 틀리지!!!! 이러고 포기했다가 새로운 방식을 접하고 다시 풀었다. 좌표 계산이 아주 더러웠던 문제이다 처음에 어항이 공중부양하는 그 파트만 잘 처리하면 나머지는 무난하게 처리할 수 있다. 수를 조절하는 부분은 그냥 BFS를 돌리면서 값 비교하고, 표에 증감표시를 해두었다가 마지막에 적용하면 된다. 4번 접는 부분은 그냥 좌표 계산해서 0행부터 4행까지 붙여 ..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 수식이 N개의 문자로 이루어져있으면, N/2 개는 연산자고, N/2+1개는 피연산자이다. 여기에 괄호가 들어갈 수 있는 곳은 각 피연산자의 앞 또는 뒤이다. 나는 괄호의 끝을 넣어준다고 생각하고 놓을 수 있는 곳들을 생각해보았다. 예제 1의 수식의 경우 저 주황색 칸들이 ')' 이 들어갈 수 있는 곳이다. 어차피 두 개의 숫자만 묶을 수 있다고 했으니까 저렇게 생각하면 충분하다. 예를..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 이해 (1,1)에서 (N,N)까지 가는 모든 경로를 탐색해야하기 때문에 BFS를 쓰던 DFS를 쓰던 상관이 없다. 근데 나는 BFS를 사용했다. 파이프는 hy, hx, ty, tx 네 개의 변수로 형상화했다. 파이프의 머리와 꼬리를 각각 (hy, hx), (ty, tx)로 만든거다. 그래서 파이프가 움직일 때 머리는 [방향벡터 + 기존 머리 좌표] 로 잡아주면 되고 ..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 이해 0부터 M-1까지의 위치 중에 세 자리를 고른다. (궁수 위치 선정) DFS를 이용했다. (삼중 for문 이용해도 ok) 3자리 다 정했으면 시뮬레이션을 돌려본다. Simulation() 근데 이 시뮬레이션이 오히려 복잡했다. 궁수 세 명 각각 BFS를 돌려서 가장 거리가 짧은 적 중에, 가장 왼쪽에 있는 적을 죽여야 한다. 근데 다른 궁수들이 같은 적을 죽일 수 있어서 바로 죽이면 안되고, 셋 ..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 이해 처음에는 그냥 단순히 하나하나 가능한 최대 크기의 색종이를 붙이는 식으로 했더니 예제는 다 통과되는데 내자마자 틀렸습니다가 떴다. 여기에 대한 반례가 하나 있는데 이렇게 되어 있으면 왼쪽 상단부터 시작을 하기 때문에 이렇게 채워진다 근데 사실 정답은 이거다, 그래서 각 좌표별로 붙일 수 있는 최대 크기의 색종이를 그냥 지정하면 안되고, 1인 경우에 사이즈1부터 5까지의 색종이들..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 이해 아주 배열을 세심하게 다뤄야 하는 문제인데, 심지어 예제가 하나밖에 없다. 그냥 본인이 여러 숫자를 넣어가면서 생각대로 잘 맵이 이동하는지를 살피는 수밖에 없다. 일단 처음 문제를 읽으면 최대 5번 이동한다고 했으니 5번의 방향을 정하는 DFS를 돌려야할 것 같다는 생각이 든다. 근데, 최대 5번이니까 1번 움직였을 때 최댓값이 나올 수도 있고 2번 움직였을..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 이해 그냥 시뮬레이션을 돌려주면 되는 문제인데, 뱀을 정의하는 방법을 조금 생각해내야 한 문제였다. 일종의 C++에서의 덱 처럼 사용할 수 있는 snake라는 배열을 만들어줬다. snake는 현재 snake의 몸이 존재하는 칸들이 순서대로 담긴다. 사과의 위치는 좌표로 받기 때문에, 받아서 바로 맵에 1로 표시해준다. 뱀이 있는 위치는 2로 표시해준다. Move_Snake() 이제 구체적으로 뱀의 ..