미소를뿌리는감자의 코딩

1. 문제https://www.acmicpc.net/problem/2493 2. 접근 방법2개의 stack을 이용해서 푸는 것이 적절하다고 생각하였다. 쏘기 전의 레이저들을 모아놓은 것을 b_shoot이라고 선언하였다.또한, [높이, 송신탑 번호] 로 저장해 두어, 추후에 레이저를 쏜 송신탑 번호를 계산하도록 하였다. b_shoot에서 하나 pop한 후, a_shoot에 저장된 값의 높이가 pop된 높이보다 작다면, 해당 a_shoot 위에 있는 블록이 b_shoot에서 pop 된 송신탑을 때린다고 생각하면 된다. 따라서, hit = [0] * n 으로 선언된 곳에, hit[b_shoot에서 pop된 송신탑 번호 -1 ] 로 저장하면 된다.만약, 작다면, break를 한 후, a_shoot에 하나의 새로..

1. 문제https://www.acmicpc.net/problem/1629 2. 접근 방법처음엔, 패턴을 찾아서 돌리는 방법으로 코드를 구현했었다.하지만, 가차없이 시간 초과가 떴고 다른 방법을 찾다가 '빠른 거듭제곱의 알고리즘' 에 대해서 알게 되었다.이는 분할 정복을 이용한 것이다.a^13의 경우 a^12 * a 와 동일하다또한 a^12의 경우 half = a^6 일 때, half * half와 동일하다.따라서 이를 이용해서, 재귀를 구현하면서 분할 정복이 가능해 지는 것이다. 3. 코드from collections import defaultdictimport sysdef remainder(a, b, c): if b == 0: return 1 elif b % 2 == 0: ..

1. 문제https://www.acmicpc.net/problem/2630 2. 접근 방법대상이 되는 사각형에서, 합이 n**2 혹은 0 이라면, blue +=1, white +=1을 해준 후, return을 해준다.만약, 이에 해당되지 않는다면, 4개로 자른 후, 다시 함수에 넣어주어야 한다. 3. 코드blue = 0white = 0def make_origami(n): origami = [] for i in range(n): ori = list(map(int, input().split())) origami.append(ori) return n, origamidef count_blue_white(left, right, up, down, origami, n): ..

1. 문제https://www.acmicpc.net/problem/8983 2. 접근 방법 동물의 위치가 (aj, bj) 라고 가정하고, 사정 거리가 L 이라고 가정한다.이 때, x1에서 동물의 위치까지의 거리를 | xi - aj | + bj 라고 문제에서 가정한다.따라서, aj에서 |xi- aj| 만큼의 거리 안에 사대가 있다면, 해당 동물을 사냥이 가능하다. 따라서, 문제의 첫 예시를 이용해서 구체화 해보도록 하겠다. 동물의 위치 좌표에서 L - y를 한 값을 y 좌표에 넣어준다. 그리고 이를 d 라고 명명한다.만약, d가 음수라면, 사대에서 겨냥할 수 없을 정도로 y 값이 컸던 것이기 때문에 이는 count에서 제외 시킨다.   (3, 3)을 예시로 들면, L 이 4이므로 x 축에서 (4-3) 인 ..