코린이 탈출기

문제 바로가기 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감�� www.acmicpc.net 청소년 상어 문제 풀면서 제대로 안 읽었다가 호되게 당한 기억이 있어서.. 이번 문제는 풀기 전에 충분히 생각하고 풀었다. 문제를 풀다보니 대충 생각하고 무작정 코드부터 짜면 로직이 꼬이거나 실수가 많아져서 결국은 시간이 더 오래걸린다는 것을 체득했다. 그래서 ! 이젠 확실히 문제를 이해할 때까지 아이패드에 적어보고 문제에서 요구하는 사항을 완벽히 이해하고 푸는 연습중이다. 이렇게 하니 코드 짜면서 헷갈릴 일이 적어서 오히려 더 빨리 ..

문제 바로가기 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 백트래킹으로 스타트 팀과 링크 팀의 팀원을 구하고, 2중 for문으로 각 팀의 점수를 계산하여 차가 가장 작은 것을 구하면 된다. 처음 풀었을 때 시간초과가 떠서 띠용.. 생각해보니 팀을 나누는 부분에서 중복계산이 있었다는 것을 찾았다. - 시간초과가 난 dfs 코드 void dfs(int digit) { if (digit == n / 2) { minn = min(minn, compare()); return; } for (int i = 0; i < n; i++) { if..

문제 바로가기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 딱 문제를 읽어보면 백트래킹 냄새가 솔솔 ~ 역시나 백트래킹으로 구현하니 아주 쉽게 풀 수 있었다 백트래킹으로 문제를 풀 때는, 기존의 상태에서 어떠한 연산이나 수행으로 바뀐 상태를 다시 원래대로 돌려놓는 것이 중요하다. dfs()함수에서 다른 상태로 갈 때 바뀌는 값이 res와 2차원 배열 visited 이므로, 재귀함수를 호출한뒤 다시 원래의 res와 visited로 돌려주어야한다. 또..

문제 바로가기 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 이해만 잘 하면 금방 풀 수 있다. 톱니바퀴 네 개가 일렬로 놓여져있고, 왼쪽 톱니바퀴의 2번째와 오른쪽 톱니바퀴의 6번째가 맞물려있는데, 회전하는 톱니바퀴 기준으로 맞물린 부분의 극이 서로 다르면 맞물린 다른 톱니바퀴도 도는 방식으로 작동한다. 따라서, 이를 DFS 백트래킹 방식으로 구현하였다. rotate(int num, int dir)가 재귀적으로 호출되며, num은 톱니바퀴 번호, dir은 톱니바퀴가 회전하는 방향 정보를 담고있다. ..

문제 바로가기 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 푸는 데 너무 힘들었던 문제 아기 상어를 BFS로 풀었던 기억이 있어서 아무 생각 없이 BFS로 풀었다가 호되게 당했다 흑흑 BFS로 하다가 DFS로 바꾸면서 로직 다 꼬이고,, 이럴 땐 그냥 덮고 그 다음날 새 마음 새 뜻으로 풀자. 그래서. 이 문제는 BFS로 풀면 안되고 재귀함수를 사용해서 DFS로 풀어야한다. 상어가 갈 수 있는 자리가 여러 곳인데, 상어의 위치를 옮기면 그때마다 물고기의 위치도 다 달라지기 때문에 상어가 움..