본문 바로가기

자바37

[백준 Silver 3] 3085 사탕 게임 - Java 문제링크 : https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 접근 과정 : 초기 상태에서 가장 많이 사탕을 먹을 수 있는 경우를 계산 사탕을 바꿀 수 있는 경우들을 탐색하며, 바꿨을 때 먹을 수 있는 사탕의 개수를 계산 사탕의 개수를 계산할 때마다, 최대값을 갱신하여 리턴. + 사탕의 실제 값은 바꾸지 않고 좌표로만 확인한다. 소스 코드 및 결과 : package BOJ; /* 사탕 게임 */ import java.io.*; public class BOJ3085 { public static void main(String[] args) throws NumberFo.. 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.
[백준 Gold 3] 2553 사회망 서비스(SNS) - Java 문제링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 접근 과정 : 각 친구는 얼리어답터이거나 일반인이다. 즉 노드의 상태가 0,1인 경우에 따라서, 최소 얼리어답터의 수를 저장하는 DP를 사용했다. DP[][] : i가 얼리어답터(1) 이거나 일반일(0)일 때, 최소 얼리어답터의 수를 의미한다. 그리고 친구 관계를 저장하는 데 있어서, List를 활용 / node 클래스 작성 두가지 방법으로 시도해보았다. 소스 코드 및 결과 : .. 2022. 1. 5.

티스토리툴바