접근법 가장 기본적인 최소 신장 트리 간선의 정보를 가중치 기준 오름차순 정렬한 뒤 사이클이 돌지 않는 선에서 선들을 이어준다. 추가 V-1만큼을 이어주면 탈출하는 조건을 넣는다면 좀 더 시간이 빨라질 것 같다. ⇒ 미묘한 성능 향상 코드 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public class BOJ_1197_최소_스패닝_트리 { static int[] parent; static int ..
접근법 구현문제. 문제가 원하는 조건에 맞게 구현을 잘하면 된다. 내가 중요하게 생각했던 부분은 bfs로 구현할 때 주변에 중복되지 않으면서 0이 아닌 빙산이 주어진다면 queue에 집어넣는다. 0이 주어진다면 방금 녹은건지 아닌지를 판단해야 한다. 이 둘 모두를 visited로 처리할 수 있다. 코드 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class BOJ_2573_빙산 { static b..
접근법 진짜 빡구현이란 이런 것이다.. 디버깅이 헬이었던 문제 최적화가 필요할 것 같다 참고한 테스트케이스 첨부하겠음 #TC 1 input: 4 2 16 16 0 32 16 4 1 4 16 32 0 2 0 8 8 correct answer: 128 output: 64 #TC 2 input: 4 0 8 1 1 8 0 1 4 8 0 8 32 1 32 32 0 correct answer: 128 output: 64 #TC 3 input: 4 2 32 16 8 4 0 4 4 0 1 8 4 32 32 0 32 correct answer: 64 output: 128 코드 package boj; import java.io.BufferedReader; import java.io.IOException; import ja..
접근법생각보다 까다로웠던 문제. 처음 접근은 가장 긴 오름차순 배열의 길이를 구하는 문제인 줄 알았다. 이 접근법은 네 가지의 문제가 있다.내림차순도 생각해야 한다는 점 ( 위에서 내려다보는 )마냥 오름차순이나 내림차순이라고 해도 건물에 가릴 수도 있다는 점몇 건물이 가리더라도 뒷 건물이 매우 크면 또 보일 수 있다는 점하나의 건물에서 좌, 우로 볼 수 있다는 점이 네 가지를 유념하면서 문제를 바라보면 다르게 생각할 수 있다. 바로 각도다. 하나의 건물을 기준으로 바라보는 각도가 밑에서 위로 올라가면서 몇 개의 건물을 볼 수 있는지를 찾으면 되는 문제 그래서 각도가 올라가면서 각도의 최댓값을 갱신할 때, 갯수를 세어 최대 갯수를 출력한다.코드package boj; import java.io.Buffere..
1229번: 육각수 육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다. 그림 1 그림1은 h1, h2, h3, h4를 의미하며, www.acmicpc.net 접근법 점화식을 잘 세우면 금방 풀 수 있는 문제 이 식을 잘 도출할 수 있다면 다음 필요한 dp를 구하는 것은 어렵지 않다. 육각수 배열을 h라 할 때, dp[n]은 h[i]값이 n을 넘지 않는 한에서, dp[n-h[i]]의 최솟값을 구하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja..
