trudy

문제https://www.acmicpc.net/problem/9465 최종 코드 package week11.baek.july19.baek;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class S9465 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(b..

문제https://www.acmicpc.net/problem/1912접근완전 탐색으로 풀면 주어진 테스트 케이스 3개는 통과하지만 시간 초과가 떠서 실패하는 문제였고, dp를 통해 풀어야 했다.  💡DP적 접근각 위치에서 끝나는 최대 부분합을 저장한다. 현재 위치에서 끝나는 최대 부분합은 이전 위치에서 끝나는 최대 부분합에 현재 값을 더한 것과 현재 값 자체 중 큰 값이 된다. 전체 배열을 순회하며 각 위치에서의 최대 부분합을 갱신해서 전역 최대값을 구한다. DP 배열을 사용하여 dp[i]를 i번째 요소로 끝나는 최대 부분합으로 정의한다. 점화식을 나타내면 아래와 같다. dp[i]=max⁡(dp[i−1]+nums[i],nums[i]) 그리고 전역 최대값을 추적하는 변수 max를 사용하여, 최종적으로 최..

문제https://www.acmicpc.net/problem/1932접근 Top-down 방식을 선택해서 풀었다.주어진 삼각형을 위와 같이 이차원 배열에 저장해줬다.그리고 아래로 한칸씩 내려가면서 숫자 합을 dp 배열에 저장했다. 세번째 줄을 예시로 들면, 18 11 16 15 가 합이 되는데, 11과 16은 그 중에서 큰 값으로 dp 배열에 저장이 된다.그 결과 오른쪽 사진과 같이 저장된다. 이 계산을 n-1줄(인덱스 n-2)까지 반복하면 마지막 줄에 최종적인 합들이 저장되게 된다. 그럼 그 중에서 가장 큰 값을 출력하면 가장 큰 합을 구할 수 있다.  최종 코드package week11.baek.july19.baek;import java.io.BufferedReader;import java.io.IO..

문제https://www.acmicpc.net/problem/2847접근그리디 알고리즘을 통해 하나씩 줄여나가면 됐던 문제이다.  최종 코드package week11.baek.july16;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class S2847 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.rea..

문제https://www.acmicpc.net/problem/1743접근대표적인 DFS 문제인데, 음식물의 길이를 구해야 했던 문제 처음에는 dfs의 depth로 음식물의 길이를 구하려고 했는데, 잘못된 접근이 이었다. # . . .. # # .# # . . 위와 같은 경우 (2,2)에서 재귀가 시작되면 depth는 (2,2), (2,3) 으로 가는 경우 2, (2,2),(2,3),(1,3) 으로 가는 경우 3 해서 최대 depth는 3이 된다.  따라서 이렇게는 음식물의 길이 4를 구할 수 없었다.   첫번째 제출 - 실패 : dfs의 depth로 길이를 구하려고 잘못 접근함package week11.baek.july16;import java.io.BufferedReader;import java.io...

문제https://www.acmicpc.net/problem/2163접근 예제 입력2 2 예제 출력3 7*5 가 있다고 하면,6번을 나눠서 7개의 1*5를 만들 것이고, 7개를 4번을 나눠서 1*1 35개로 만들 수 있다.  이것을 식으로 나타내면(N-1) + N * (M-1); 최종 코드package week11.baek.july16;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class B2163 { public static void main(String[] args) throws IOException { BufferedR..

문제https://www.acmicpc.net/problem/2903접근 알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.정사각형의 각 변의 중앙에 점을 하나 추가한다.정사각형의 중심에 점을 하나 추가한다.초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.  n=1 사각형이 1개 -> 4개 점 5*1개 추가 n=2사각형이 4개->16개점 5*4 - 4*1 (=16)개 추가 진짜.... 너무 어렵게 접근했다한 변의 점이 몇 개인지만 파악하면 쉽게 풀 수 있었는데! 초기상태 : 점 2개n=1 일 때는 점 2+1개n=2 일 때는  점 3+2개n=3일 때는 ..

문제https://www.acmicpc.net/problem/1012접근 밭이 위처럼 있을 때, 배추흰지렁이는 배추끼리 인접해있는 곳을 지나갈 수 있다고 하니까, 1로 된 덩어리의 개수를 구하면 되는 대표적인 dfs/bfs 문제 였다.  최종코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static boolean[][] visited; static int[][] map; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, -1,..

문제https://www.acmicpc.net/problem/1673접근강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환할 수 있다.강민이가 지금 갖고 있는 치킨 쿠폰으로 치킨을 최대 몇 마리나 먹을 수 있는지 구하여라. 단, 치킨을 주문하기 위해서는 반드시 치킨 쿠폰을 갖고 있어야 한다. 예제 입력4 310 3100 5 예제 출력514124  쿠폰 4장을 가지고 있고, 도장 3개에 쿠폰 1장을 주는 경우쿠폰 3장을 통해 3마리를 시키고, 쿠폰 한 장을 더 받는다. 나머지 쿠폰 두 장을 통해 두 마리를 더 시킨다.  => 총 5마리 쿠폰 10장을 가지고 있고, ..

문제https://www.acmicpc.net/problem/14487 접근둘째 줄에 i번째 마을과 i+1번째 마을의 이동비용 vi가 n개 주어진다. n번째 vi는 n번째 마을과 1번째 마을의 이동비용을 의미한다. (1 ≤ vi ≤ 1,000) 1 6 5 2 4 n=51 : 1번째 - 2번째 마을6 : 2번째 - 3번째 마을5: 3번째 - 4번째 마을2: 4번째 - 5번째 마을4: 5번째 - 1번째 마을  원형이라서 모든 곳을 다 돌아야해서 똑같은 거 아닌가..? 했지만 생각해보니 가장 비싼 한 곳만 안들리도록 하면 됐었던 문제최종 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;impor..