BOJ
[BOJ / 비트마스크 DP] 1102 발전소
www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 1102 발전소 알고리즘 : 비트마스크 DP / BFS 비트마스크를 DP배열의 iterator로 사용하는 문제입니다. dp를 이용해 현재 적용중인 상태에서 이미 들린 상태이거나 이미 결과값을 초과한 경우 가지치기를 하면 됩니다. 문제에서 해결이 안되는 경우에는 -1을 출력하라고 했으나, 모든 발전소는 다른 모든 발전소를 킬 수 있으므로 즉, 키는 비용에 음수값이 주어지는 경우가 없으므로 -1을 출력하는 경우는 모든 발전소가..
[BOJ / DP] 15990 1,2,3 더하기 5
www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 15990 1,2,3 더하기 5 알고리즘 : DP 1차원 배열 DP로 시도하다가 점화식에 문제가 있다는 걸 발견하고 3차원 배열 DP로 바꾸었습니다. 같은 수를 두번 이상 연속해서 사용하면 안되므로 1차원 배열 DP에서 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 에서 dp[i-1]에서 +1로 끝나는 dp[i-2]를 빼고 dp[i-2]에서 dp[i-4]를 빼고 dp[i-3]에서 dp[i-6]을 빼려다 빼는 부분에서도 다시 빼야하는 경우가 있어..
[BOJ / 위상정렬] 1516 게임개발
www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 1516 게임개발 알고리즘 : 위상정렬, 우선순위큐 전체적으로 풀면서 다익스트라 느낌이 드는 문제였습니다. 다익스트라와 위성정렬 문제를 풀어본 적이 있다면 쉽게 풀이할 수 있습니다. 위상정렬로 inDegree가 0인 아이들만 우선순위 큐에서 관리하면 됩니다. #include #include #include #include #include #include #include #include..
[BOJ / 삼성A형기출] 13460 구술 탈출 2
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 13460 구술탈출 2 알고리즘 : BFS 완전탐색문제이며 탈출구가 트리의 끝이 아닌 중간에 있을 가능성이 존재하고 지금까지 구..