[백준/BOJ] 1149 RGB거리 - JAVA - 실버1문제https://www.acmicpc.net/problem/1149문제 분석조건N개의 집이 일렬로 있다.각 집은 빨강, 초록, 파랑 중 하나로 칠해야 한다.서로 인접한 두 집은 같은 색으로 칠할 수 없다.모든 집을 칠하는 비용이 주어질 때, 전체 최소 비용을 구하는 문제이다.풀이방법i번째 집을 칠할 때는, 바로 앞 집과 같은 색을 사용할 수 없다는 제약이 존재한다.따라서 i번째 집을 빨강으로 칠한다면, i-1번째 집은 초록이나 파랑으로 칠해야 한다.이 원리를 바탕으로, 현재 집을 어떤 색으로 칠할지를 결정할 때는 이전 집에서 가능한 두 가지 색 중 더 적은 비용을 선택하여 누적해나가는 방식으로 최소 비용을 구할 수 있다.점화식에 따라 각 집을 어..

[백준/BOJ] 14889 스타트와 링크 - JAVA - 실버1문제https://www.acmicpc.net/problem/14889문제 분석조건짝수인 N명을 2팀으로 나누고, 각 팀의 시너지 차이를 최소화하는 문제이다.풀이방법비트마스킹을 사용하여 팀을 나누어주었다.시작 조합은 각 팀에 N/2명만큼 있어야하므로 조합의 시작 부분을`1 `for (int i = 1 ; i ; i++)` 조합을 구하고 팀원수가 맞는다면 각 팀의 시너지를 구해주었다.+마지막 팀원을 고정하고 첫 부분도 고정은 했지만 비트마스킹 특성상 어쩔수없이 `1 i 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import ..

[백준/BOJ] 2606 바이러스 - JAVA - 실버3문제https://www.acmicpc.net/problem/2606문제 분석조건네트워크로 연결된 컴퓨터들 사이에서 1번 컴퓨터와 연결된 컴퓨터의 수를 구하는 문제이다.풀이방법많은 문제를 BFS를 활용하며 해결하므로 DFS를 통해 문제 해결을 해보았다.DFS를 구현하여 문제를 해결할 수 있는데 1번 노드를 제외한 연결된 노드의 수를 출력하므로 마지막에 `-1`를 해주었다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static boolean[][] graph..

백준 BOJ 11053 가장 긴 증가하는 부분 수열 - JAVA - 실버2문제https://www.acmicpc.net/problem/11053문제 분석조건첫째 줄에 수열의 크기, 둘째 줄에 수열이 주어짐가장 긴 증가하는 부분 수열의 길이 출력풀이방법LIS 알고리즘을 활용하여 풀이코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Bu..

백준 BOJ 14939 불 끄기 - JAVA문제https://www.acmicpc.net/problem/14939문제 분석조건방의 크기는 10X10으로 일정하다.불이 켜진 곳은 'O', 꺼진 곳은 '#'으로 표현된다.스위치를 누른 곳과 상하좌우의 상태가 반전된다.모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수 출력모두 끌 수 없을 경우 -1 출력풀이방법하나의 스위치 상태를 바꾸면 상하좌우가 전부 반전되므로 1행의 상태가 결정이 된다면 그 아래는 자동으로 결정됨한 행의 스위치가 10개이므로 총경우의 수는 2^10개로 많지 않음위 행을 기준으로 켜진 스위치를 끈다면 해당 행의 윗 행은 전부 스위치가 꺼지게 됨마지막 행에서 위 행을 기준으로 스위치를 껐을 때 켜져 있는 스위치가 남아있을 경우 불가..

[백준/BOJ] 1520 내리막 길 - JAVA - 골드3문제https://www.acmicpc.net/problem/1520문제 분석조건왼쪽 위에서 시작하여 오른쪽 아래로 이동하는 것이 목표현재 숫자보다 작은 인접한 숫자로만 이동할 수 있음가능한 경로의 수를 출력풀이방법DFS를 이용하여 경로를 탐색하며 DP를 이용하여 방문했던 점엔 다시 방문하지 않는 방법을 이용했습니다.DP 테이블을 -1로 초기화 한 뒤 출발지점부터 탐색을 시작현재 좌표에 이미 방문을 했으면 현재 좌표의 DP값을 반환하고, 첫 방문(-1)일 시 0으로 DP값을 업데이트DFS 탐색을 시계방향으로 했을 때 아래와 같은 상황이 된다.방법을 반복하여 목표 지점에 도달하였을 경우 1를 반환하고 이를 이전 좌표 DP값에 업데이트 한다.DP값을 ..