목록2024/09 (49)
미소를뿌리는감자의 코딩
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) 인 ..
1. 문제https://www.acmicpc.net/problem/2805 2. 접근 방법처음엔, tree 높이를 sort() 한 후, 높이에 따른 잘라지는 나무의 높이를 알아내고, 해당 높이가 원하는 높이보다 작을 시, 잘라지는 높이에 따른 4*x, 3*x, ... 을 해주려고 했고, 코드를 작성하기도 하였다.def get_max_h(n, wanted_height, trees): for i in range(n): left = 0 for j in range(i+1, n, 1): left += trees[j] - trees[i] if left 해당 방법이 상당히 괜찮다고 개인적으로 생각하였지만, O(n^2)의 한계로 시간 초과 통과를 하지 못..
1. 문제https://www.acmicpc.net/problem/2468 2. 접근 방법최대 개수의 안전 지점을 얻어야 하기에, height를 min_height -1 에서 max_height까지 잠긴다고 가정하고 문제를 풀어야 한다. 왜냐하면 노트에 '아무 지역도 물에 잠기지 않을 수도 있다.'라고 적혀 있기 때문이다. 물에 잠기지 않은 지점이 나타나게 되면, 해당 지점으로부터 위, 아래, 왼쪽, 오른쪽으로 잠기는 지점이 있는지 없는지 유무를 판별한다.해당 함수가 호출 될 때마다 count + 1을 하여 안전 지역 개수를 높여준다. 처음에는 이를 stack이 아닌, 재귀로 접근해서 풀었다.하지만 recursion error가 발생하여, stack으로 접근하여 풀었어야 한다.def make_grey(i..
1. 문제https://www.acmicpc.net/problem/23092. 접근 방법일단 주어진 height를 다 더한 후 100을 빼 주어, 초과되는 height를 구하였다.'초과 된 height = 백설 공주와 일곱 난쟁이가 아닌 두 난쟁이'를 의미하게 될 것이다. 따라서, 주어진 height 중 2개의 height의 합이 초과 된 height를 나타내는 수들을 찾기 시작할 것이다. 만약, 해당 조건을 만족시키는 두 수를 찾게 되면 해당 두 수를 제외한 나머지를 list 로 저장을 하게 되고, sort() 후 출력하면 된다. 3. 코드def find_stranger(): height = [] for i in range(9): height.append(int(input()))..