DP10 [백준 Gold 3] 1516 게임 개발 - Java 문제링크 : https://www.acmicpc.net/problem/status/1516 1516번 맞힌 사람 - 1 페이지 모든 언어C++JavaPythonCC++17Java 8Python 3C11PyPy3C99C++98C++11C++14Java 8 (OpenJDK)Java 11C++20Python 2PyPy2RubyKotlin (JVM)Kotlin (Native)CythonSwiftTextC#node.jsGoGo (gccgo)Java 15DD (LDC)F# (Mono)PHPRust 2015Rust 2018PascalScalaLuaPerlRakuRuby 1.8R www.acmicpc.net 접근 과정 : 어떤 건물을 짓기 전에, 지어야 하는 건물이 있다면 그 건물들을 모두 먼저 지어야 한다. 건물을 .. 2022. 1. 27. [백준 Silver 1] 11048 이동하기 - Java 문제링크 : https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 접근 과정 : 해당 문제는 DP를 이용해서 풀수 있다. DP[r][c] = maze[r][c] + Math.max(dp[r-1][c], Math.max(dp[r][c-1], dp[r-1][c-1])) 이다. Top-down 과 Bottom-up으로 풀어보았다. 소스 코드 및 결과 : package BOJ; /* 이동하기 Top-down */ import java.io.*.. 2022. 1. 7. [백준 Gold 1] 2213 트리의 독립집합 - Java 문제링크 : https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 접근 과정 : 이전에 풀었던, '트리에서의 다이나믹 프로그래밍' 접근을 통해서 문제를 해결하려고 했다. 추가적으로 고민했던 부분은 독립 집합의 원소들을 추적하는 부분이었다. 결국 현재 정점의 독립 집합 포함 여부에 따라서 연결된 다음 정점의 포함여부가 결정되기에, 이 부분을 고려해서 작성했다. DP[][] : i번 정점의 독립집합 포함 여부 , [n+1.. 2022. 1. 6. [백준 Gold 1] 1949 우수 마을 - Java 문제링크 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 접근 과정 : 특정 마을이 우수 마을인지 아닌지를 기준으로하는 DP를 사용했다. DP[][] : i 마을이 우수 마을인 경우(1) / 우수 마을이 아닌 경우(0) 의 우수 마을들의 인구 총합 마을간의 연결 관계는, town 클래스를 생성해서 사용했다. '트리에서의 다이나믹 프로그래밍' 을 풀어보았다면 어렵지 않게 해결할 수 있다. 소스 코드 및 결과 : package BOJ;.. 2022. 1. 5. 이전 1 2 3 다음
