undefined behavior
코딩하다보면, undefined behavior를 생각할 때가 있다.
틈날 때마다 보기위해 여기 링크를 걸어둔다.
[PS] BOJ 20543번 폭탄 던지는 태영이
https://www.acmicpc.net/problem/20543 (혹시나 풀어보실 분들은 알고리즘 분류를 보지 않고 풀어보길 권장합니다.) 이 문제를 처음 보고, 간만에 신선하다는 느낌을 받았다. 어떤 알고리즘이나 자료구조를 알고 있으면, 흔히 많이 나오는 유형에 속하는 문제가 있는가 하면, 그렇지 않은 문제도 있다. 이 문제를 풀면서 규칙을 찾고 시간을 단축시켜 나가는 과정이 재미있었고, 예전에 수학에 매력을 느꼈을 때의 느낌과 비슷했다. 물론, 영문까지 포함한 많은 문제를 풀어본 건 아니지만 부족한 내가 느끼기에는 그랬다. 어려운 자료구조를 쓰지 않아도 (기본적인 재료로도) 충분히 난이도를 높여 갈 수 있는 (까다로우며 맛있는 요리?) 그런 문제들의 초입에 해당하지 않나 싶다. 아래는 풀이를 생각한 순서이다. 1. 출력은 맞지만 시간초과 풀이 2. 정답 풀이 먼저, 제한도 까다롭지 않고 시간도 2초나 주어졌기 때문에 풀어보는 것이 중요하다고 생각했다. N이 2,000일 때, 2차원 배열의 데이터 개수는 2,000 x 2,000 = 4,000,000 이다. O(n)에 해당하는 과정은 시간초과를 발생시키지 않으나, 폭탄을 찾기 위해서 자기 자신의 위치(arr[i][j])에서 가능한 모든 경우의 수를 찾으려고 하면 시간초과가 뜰 것이다. 여기까지 생각하고, 규칙을 생각해보았다. 예제 입력과 예제 출력들을 보면서, 가장 외곽에 위치한 배열의 원소들부터 채워가면 될 것이라고 생각했다. 먼저, (0, 0)부터 시작한다고 하면, 시계방향으로 테두리를 돌면서 1칸씩 안쪽으로 진행해볼 수 있다. 그러나 가장 첫 줄을 시물레이션 해보면, 우리가 이중 for문을 통해 배열을 탐색하는 일반적인 과정으로도 채워나갈 수 있다는 것을 알게 되었다. 왜냐하면, 폭탄이 있을 수 없는 구역이 존재하기 때문이다. (m = 1의 경우는 예외) m이 1인 경우에는 그대로 절댓값으로 바꿔서 출력하면 되고, m이 3이상의 홀수인 경우에 생각해보면, 외곽 테두리에 ...
댓글
댓글 쓰기