DP

CS/PS
[BOJ] 9466, 1202, 14003, 2166
BOJ 9466 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 문제이다. 크게 어렵지는 않은데, 주의할 만한 점은 vertex의 개수가 100000이므로 (edge의 개수도 당연히 100000이다) 모든 정점에 대해 BFS를 수행하면 O(VE)니까 TLE가 뜬다. 따라서 한 번 방문한 vertex에 대해서는 다시 방문하면 안 되고, cycle이 발생하는 경우에도 잘 체크를 해 줘야 한다. 어떤 방식으로든 한 번 방문한 ver..
→2021.09.01
CS/PS
[BOJ] 1462번 : 퀴즈쇼
https://www.acmicpc.net/problem/1462 1462번: 퀴즈쇼 첫째 줄에 문제의 개수 N과 보너스 점수를 얻는데 필요한 코인의 개수 M이 주어진다. (1 ≤ N, M ≤ 500,000) 둘째 줄에는 각 문제에 해당하는 점수가 1번 문제부터 주어지고, 셋째 줄에는 각 문제에 www.acmicpc.net 아주 재미있는 DP 문제이다. 얼핏 보면 2006정올 도대회 초등부 4번 '계단 오르기'(https://www.acmicpc.net/problem/2579)와 비슷해 보이지만 다르다. 처음엔 비슷한 문제로 보고 접근했다가 틀렸다. 가장 다른 점은 현재 풀고 있는 문제 i와 현재 가지고 있는 코인 개수 j를 가지고 2차원 DP table을 짜면 time complexity와 space ..
→2021.07.14
CS/PS
[BOJ] 1028번 : 다이아몬드 광산
https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 그다지 어렵지는 않은 DP 문제이다. 다만 한 가지 아이디어가 중요한데, 마름모가 네 변으로 구성되므로 그 네 변의 길이를 brute-force로 구하지 말고 memorization을 사용해서 구하겠다는 아이디어만 내놓으면 된다. 나는 먼저 UpRight방향, UpLeft방향, DownRight방향, DownLeft방향에 대해서 그 map을 마지막으로 하는 가장 긴 연속적인 1의 길이를 DP table에 저장하였다. 이 과정에서는 directi..
→2021.07.05

• 이전
• 1
• 다음