[문제 링크]https://www.acmicpc.net/problem/1697문제 설명수빈의 위치 N, 동생의 위치 K에 있고, 수빈이 이동해서 동생을 찾는다.수빈의 위치가 X일 때 걸으면 1초 후에 X-1 또는 X+1, 순간이동하면 1초 후 2 * X동생을 찾을 수 있는 가장 빠른 시간을 구한다. 문제 풀이BFS로 풀이걷거나 순간이동하는 것에 상관없이 수빈이가 이동할 수 있는 방법은 3가지이다.X + 1X - 1X * 2 현재 수빈이의 위치에서 위 3가지 방법으로 이동할 수 있는 위치와 해당 위치로 이동하는 데 걸린 시간을 큐에 담는다. 이미 수빈이가 위치했던 곳은 중복해서 가지 않기 위해 boolean 배열 visited로 방문 체크한다.큐에서 하나씩 꺼낼 때마다 동생의 위치 k와 같은지 비교해..

[문제 링크]https://www.acmicpc.net/problem/1149문제 설명1 ~ N 번의 집을 아래 규칙을 따라서 빨강, 초록, 파랑 중 하나를 골라 색을 칠하는 데 드는 비용의 최솟값을 구한다.1. 1번 집의 색 != 2번 집의 색2. N번 집의 색 != N-1번 집의 색3. i번 집의 색 != i-1번, i번 집의 색 != i-2번 집의 색 문제 풀이다이나믹 프로그래밍으로 풀이N번째 집의 색이 빨간색이라면, N+1번째 집의 색깔은 초록색 or 파란색N-1번째 집의 색깔은 초록색 or 파란색dp 테이블은 2차원 배열로, column은 순서대로 빨간색(0), 초록색(1) , 파란색(2)이다.dp[i][j]는 i번째 집을 j 색으로 칠했을 때, 0~i번 집을 칠하는 데 드는 비용의 최솟값..

[문제 링크]https://www.acmicpc.net/problem/13335문제 설명길이가 w, 최대하중 L인 다리를 n개의 트럭이 순서대로 건너간다.동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 L보다 작거나 같아야 한다.모든 트럭이 다리를 건너는 최단시간을 구한다. 문제 풀이문제에 주어진 그대로 구현하는 구현 문제idx : 현재 트럭의 번호onBridgeW 리스트: 다리 위에 올라가 있는 트럭들 무게의 합onBrdigeIdx : 다리 위에 올라가 있는 트럭들의 번호를 담고 있는 리스트distance 배열 : 각 트럭마다 다리 위를 이동한 거리를 계산한 배열move() : 다리 위에 올라가 있는 트럭들이 이동한 거리를 1씩 증가하는 메서드idx번 트럭의 무게 + onBridgeW 한 ..

[문제 링크]https://www.acmicpc.net/problem/21921문제 설명블로그를 시작한 지 N일이 지났을 때, X일 동안 가장 많이 들어온 방문자 수와 그 기간의 개수를 구해서 출력한다.최대 방문자 수가 0명이면 SAD 출력 문제 풀이슬라이딩 윈도우 알고리즘을 활용한 문제첫 번째 X일 동안의 방문자수(1일차~X일차) 합을 먼저 구한다.for문으로 한 칸씩 이동하면서 맨 앞의 값은 빼고 새로운 값을 더해서 구간의 합을 계산한다. 전체 코드import java.io.*;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { ..

[문제 링크]https://www.acmicpc.net/problem/14719문제 설명테두리 있는 글상자 문제 풀이구현 문제for문을 돌면서 현재 블록 기준으로 오른쪽에서 최대 높이의 블록, 왼쪽에서 최대 높이의 블록을 각각 구한다.→ maxLeft, maxRightmaxLeft와 maxRight 중 더 작은 값 m을 구한다.m이 현재 블록의 높이보다 높을 경우 빗물이 고인다.→ m - (현재 블록의 높이) 가 현재 블록에 쌓이는 빗물의 양이 된다.여기서, 가장 왼쪽 블록과 가장 오른쪽 블록에는 물이 고일 수 없다.따라서 for문의 범위는 1 부터 w-1예제2를 그림으로 그려보면 아래와 같다. 전체코드import java.io.*;import java.util.Arrays;import ja..

[문제 링크]https://www.acmicpc.net/problem/1926문제 설명n × m 크기의 도화지에 있는 그림의 개수와 그림의 넓이가 가장 큰 것을 구한다.0은 색칠이 안된 부분, 1은 색칠이 된 부분이고, 1로 연결된 것을 그림 이라고 한다. 문제 풀이(1) DFS 사용import java.io.*;import java.util.StringTokenizer;public class Main { static int[][] array; static int n, m; static int area = 0, cnt = 0, maxArea = 0; static boolean[][] visited; static int[] dx = {-1, 1, 0, 0}; sta..