Algorithm/BOJ172 [BOJ]4179번: 불! 문제: https://www.acmicpc.net/problem/4179 시뮬레이션 문제입니다. 같은 시점에 지훈이와 불은 같은 좌표에 있을 수 없기에, 큐에 불을 먼저 넣고, 지훈이의 좌표를 넣어줘서 불이 있는 좌표는 지훈이가 방문하지 못하도록 했습니다. R,C 제한이 크므로 BFS를 한 번만 돌아서 해결해야하는 문제입니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ4179.cc 2020. 7. 2. [BOJ]14501번: 퇴사 문제: https://www.acmicpc.net/problem/14501 모든 경우를 다 구해봐야 하므로 DP 문제입니다. 제가 세운 점화식은 다음과 같습니다. dp[day][revenue]: 특정 DAY까지 revenue를 벌었을 때의 상태를 저장했습니다. dp[day][revenue] = max(특정 day 일을 하거나, 특정 day 일을 안하거나) 이렇게 나눌 수 있습니다. 특정 day 상담 일을 한다면 다음 날짜는 day 상담기간만큼 JUMP 할 것이고 특정 day 상담 일을 안한다면 day + 1 상담을 할 지 말지 결정하는 로직으로 넘어가면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ14501.cc 2020. 7. 2. [BOJ]1411번: 비슷한 단어 문제: https://www.acmicpc.net/problem/1411 문제 이해 못해서 멍때렸던 문제입니다. 최대 100개에 대해 2개씩만 비교하면 되니 100 combination 2의 경우의 수로 완전탐색이 가능합니다. 두 개씩 뽑아서 아래 사항들을 비교해주면 됩니다. 1. 길이가 같은지 2. 이미 매칭된 알파벳이 다른 알파벳과 매칭되었는지 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1411.cc 2020. 7. 1. [BOJ]2668번: 숫자고르기 문제: https://www.acmicpc.net/problem/2668 유형 태그가 다양한 걸 보니 푸는 방법은 다양한 것 같습니다만, 싸이클 찾기 문제로 해결했습니다. N = 100이니 직접 하나씩 뽑아보면서 탐색하면 터지는 건 자명합니다. 문제 예제를 보면 표에서 첫번째 줄에 5번 칸이 -> 5로 가는 걸 볼 수 있습니다. 이걸 보고 자기 자신의 숫자를 가지는 애들이 정답 갯수에 포함된다면, 정답으로 뽑히는 애들은 싸이클 성질을 가지고 있다는 걸 알았습니다. 즉, 이 문제는 가장 큰 싸이클을 구하는 문제입니다. 싸이클을 찾는 방법은 위상정렬을 통해 해결하였습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2668.cc 2020. 6. 26. 이전 1 ··· 32 33 34 35 36 37 38 ··· 43 다음
