Algorithm202 BOJ 20005 - 보스몬스터 전리품 문제 백준 온라인 저지 - 20005번 풀이 과정 해당 문제는 pypy3로 풀이했습니다. 몬스터와 플레이어의 위치가 주어질 때 몬스터를 처치해서 보상을 얻을 수 있는 플레이어의 수를 구하는 문제입니다. 플레이어는 몬스터에게 최단 거리로 이동하기 때문에 BFS 를 이용해서 몬스터 까지의 최단 경로룰 구하면 됩니다. 이때 상태공간 S 는 다음과 같이 정의할 수 있습니다. S[x][y][player] = (x, y) 지점에 player 가 이미 방문한 적이 있는지 유무 한 가지 실수를 했던 점은 `BFS` 가 종료되기 위한 조건으로 `queue` 가 비어있는지를 체크한 것인데, 사실 더 이상 이동할 곳이 없더라도 몬스터의 체력이 0 이하가 될 때까지 게임을 진행해야해서 계속 틀렸었습니다. 따라서 이 부분만 유.. 2021. 3. 14. BOJ 17521 - Byte Coin 문제 백준 온라인 저지 - 17521번 풀이 과정 바이트 코인 의 시세가 주어질 때 매수 및 매도를 통해 얻을 수 있는 최대 이익을 계산하는 문제입니다. 매수 및 매도 횟수에 제한이 없기 때문에 그래프의 극대 및 극소 지점에서 매도 및 매수를 진행하는 그리디 해법이 적용됩니다. 각각의 순회에서 이전 가격과 비교하여 그래프의 상승 및 하강을 파악할 수 있으며 마지막에 매도하지 않고 남은 코인이 존재할 경우 이전에 극소 지점에서 코인을 구매하고 아직 판매하지 못한 것이기 때문에 극대 지점을 갱신 중인 상황이라는 것을 의미하고 따라서 마지막 날의 시세에 팔면 최대 이익을 취할 수 있습니다. 코드 import sys N, W = list(map(int, sys.stdin.readline().split())) c.. 2021. 3. 14. BOJ 20363 - 당근 키우기 문제 백준 온라인 저지 - 20363번 풀이 과정 물과 햇빛을 주는 규칙이 주어질 때 목표 수치로 도달하기 위한 최소 횟수를 구하는 문제입니다. 예시로 햇빛과 물의 목표치가 123456, 12345 일 경우를 생각해보겠습니다. 10 으로 나눈 몫 만큼 반대편 수치가 줄어들기 때문에 첫번째 시도에는 두 수치중 큰 수치를 먼저 만족시키는게 유리합니다. 그런데 이때 123456 을 딱 맞춘 다음 12345 를 만족시키는 경우와 123456 보다 더 많은 수치를 부여한 뒤 12345 를 만족시키는 이 두 가지 경우에서 어떤 것이 더 적은 횟수의 양분 공급을 필요로 할까요? 10 으로 나눈 몫 만큼 반대편 수치가 줄어들기 때문에 첫번째 경우 1234, 123, 12, 1 순서대로 양분 공급이 필요합니다. 즉 첫번.. 2021. 3. 14. BOJ 14588 - Line Friends (Small) 문제 백준 온라인 저지 - 14588번 풀이 과정 선분의 겹칩 유무를 이용해서 각 선분간의 최소 거리 값을 구하는 문제입니다. 모든 선분간의 최소 거리 정보를 알아야하고 N 이 최대 300 이기 때문에 플로이드 와샬 알고리즘을 활용했습니다. 문제를 해결하고 선분 겹칩 연산과 관련해서 다른 분의 제출 코드를 확인해봤는데 다음과 같은 좋은 방법도 있는 것을 알게 되었습니다. a1, b1 = 선분 1 양 끝점 a2, b2 = 선분 2 양 끝점 if max(a1, a2) pivot[1]: return False elif opponent[1] < pivot[0]: return False return True def make_graph(): dist = [[sys.maxsize] * N for _ in range(.. 2021. 3. 14. BOJ 14925 - 목장 건설하기 문제 백준 온라인 저지 - 14925번 풀이 과정 가장 큰 정사각형을 찾는 동적 계획법 문제입니다. 그냥 완전 탐색 으로 찾으려 할 경우 O(N^4) 이기 때문에 시간 초과가 발생하게 됩니다. dp[x,y] = (x, y)지점을 왼쪽 모서리로 하는 가장 큰 정사각형의 한 변의 길이 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다. dp[x][y] = min(dp[x + 1][y], dp[x][y + 1], dp[x + 1][y + 1]) + 1 이때 격자를 벗어나는 위치나 장애물이 있는 경우를 기저 사례로 처리해줍니다. 코드 import sys sys.setrecursionlimit(10**6) M, N = list(map(int, sys.stdin.readline().split())) board.. 2021. 3. 14. BOJ 13164 - 행복 유치원 문제 백준 온라인 저지 - 13164번 풀이 과정 그리디 문제가 항상 그렇듯 풀이는 정말 간단한데 아이디어를 생각하는게 어려운 문제였습니다. K 개의 그룹을 만들어야하고 모든 키 정보는 양수라는 점을 이용해서 처음에는 2명 이상의 그룹의 수를 최소화 하는 방향으로 접근했습니다. 여기서 그룹의 인원수는 무조건 적은게 좋다고 생각해서 2인 그룹 의 수를 최소화 할 수 있는 방향으로 고민했었습니다. 그런데 이렇게 접근하니까 최적해를 고르는 명확한 기준을 잡기가 어려웠고 상황에 따라서는 모순이 생기는 경우도 있었습니다. 결국 다른 방법이 필요했는데 타 블로그의 풀이를 참고해서 문제를 해결할 수 있었습니다. 그룹의 수가 K 일 때 그룹의 경계는 K - 1 개 만큼 존재합니다. 여기서 이 경계 값들을 최대화해서 그.. 2021. 3. 14. 이전 1 ··· 13 14 15 16 17 18 19 ··· 34 다음
