본문 바로가기

개발공부/알고리즘

백준 12869번 - 뮤탈리스크 [DP/자바 JAVA] https://www.acmicpc.net/problem/12869 🚀 문제  엄청 고민하고 어렵게 풀어낸 문제다. '뮤탈리스크'를 오랜만에 들으니 너무 반가웠지만 문제는 나를 전혀 반겨주지 않는 난이도의 문제였다. 슬프지만 100% 자력으로 풀지는 못 했고, 아래 블로그를 참고해서 풀어냈다.  https://velog.io/@gandi0330/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Java-%EB%B0%B1%EC%A4%80-%EB%AE%A4%ED%83%88%EB%A6%AC%EC%8A%A4%ED%81%AC-12869🚀 사고방식  뮤탈리스크의 공격 한번에 세 개의 SCV가 각각 9,3,1씩 체력을 잃는다.(현실 반영 ㅋㅋㅋㅋ)  때리는 순서에 따라서 공격력이 바뀌니까 공격 해.. 더보기
백준 13398번 - 연속합 2 [DP/자바 JAVA] https://www.acmicpc.net/problem/13398 🚀 문제  🚀 사고방식  연속합 문제의 시리즈 문제다. 이전 문제: https://captain-turtle.tistory.com/entry/%EB%B0%B1%EC%A4%80-1912%EB%B2%88-%EC%97%B0%EC%86%8D%ED%95%A9-DP%EC%9E%90%EB%B0%94-JAVA 백준 1912번 - 연속합 [DP/자바 JAVA]https://www.acmicpc.net/problem/1912  사고방식 dp[i] 값을 구해줄 때 다음 두 가지만 비교하면 된다.    1) dp[i-1] + arr[i]가 큰지    2) arr[i]가 큰지.  이렇게 해두면 dp[i-1] 에는 1~i-1 값 중 연속된 몇 개captain.. 더보기
백준 9465번 - 스티커 [DP/자바 JAVA] https://www.acmicpc.net/problem/9465 🚀 문제   또 다른 DP문제이다. 런타임 에러가 떠서 애를 좀 먹었지만, 어렵지 않게 잘 풀어냈다!  🚀 사고방식열을 기준으로 생각하자. arr[i][j]에는 입력값. 즉, 스티커의 점수를 받고, dp[i][j]에는 i,j 위치에 도달할 때까지의 최고 점수를 넣는다.  즉, 다음 표와 같다. 1,11,21,31,41,52,12,22,32,42,5 dp 배열의 1,3 위치(dp[1][3]) 에는 arr (1,1), (2,2), (1,3)의 합이나 arr (2,1), (1,3)의 합 중 큰 값이 들어간다.  문제에서 550 10 100 20 4030 50 70 10 60을 주었으므로 dp[1][3]은 50+50+100 혹은 30+100 .. 더보기
백준 2225번 - 합분해 [DP/자바 JAVA] https://www.acmicpc.net/problem/2225   결론 import java.util.Scanner;public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int dp[][] = new int [201][201]; for(int i=0; i 더보기
백준 1699번 - 제곱수의 합 [DP/자바 JAVA] https://www.acmicpc.net/problem/1699   결론 import java.util.Scanner;public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int dp[] = new int [100001]; for(int i=0; i 더보기
백준 1912번 - 연속합 [DP/자바 JAVA] https://www.acmicpc.net/problem/1912  사고방식 dp[i] 값을 구해줄 때 다음 두 가지만 비교하면 된다.    1) dp[i-1] + arr[i]가 큰지    2) arr[i]가 큰지.  이렇게 해두면 dp[i-1] 에는 1~i-1 값 중 연속된 몇 개 수를 선택하여 구할 수 있는 가장 큰 합이 저장되어 있다.(이때, i-1번째 수는 무조건 포함)-> dp[i]를 구할 때는 이전 값들의 합에 i번째 수를 더하는게 큰지, 아니면 이전 값들은 버리고 i번째 수만 사용하는게 더 큰지 비교해주면 된다.  따라서, dp[i] = Math.max(arr[i], arr[i]+dp[i-1])를 해주면 i번째 수를 포함하며 1~i 번째 수 중 연속된 몇 개 수를 선택하여 구할 수 있는 가장.. 더보기
백준 14002번 - 가장 긴 증가하는 부분 수열 4 [DP/자바 JAVA] https://www.acmicpc.net/problem/14002  사고방식 아직은 쪼랩이어서..ㅎㅎ 골드 문제라고 하면 괜히 어렵게 느껴진다..ㅎㅎ 하지만 잘 풀었따! 카타르시스 왕창!  다행힌거는 가장 긴 증가하는 부분 수열 이전 문제를 풀었었기 때문에 조금 수월했다. 이 전에는 가장 긴 숫자들 갯수만 구하면 됐지만 이제는 그 숫자들이 뭐인지까지 정확히 출력해내야해서 어려웠다.  먼저 가장 긴 증가하는 부분 수열 길이는 https://captain-turtle.tistory.com/entry/%EB%B0%B1%EC%A4%80-11053%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%8.. 더보기
백준 11053번 - 가장 긴 증가하는 부분 수열 [DP/자바 JAVA] https://www.acmicpc.net/problem/11053  사고방식 볼 때마다 느끼지만 백준 선생님께서 문제 이름 정하는 과정이 너무 궁금하다. 가장 긴 증가하는 부분 수열. ㅋㅋㅋㅋㅋ. 너무 맞는 말이지만 문제 이름이 가장 긴 증가하는 수열 부분 이라고 하니 웃기다. 아니 부분 수열.  문제는 꽤 쉽다. 입력 값으로 수열에 들어갈 숫자들이 주어지면 숫자들을 건너뛰면서 생각하며 가장 길게 증가하는 구간의 숫자가 몇 개인지 구하면 된다.  arr 배열에는 입력값들을 넣고, dp 배열에는 가장 긴 배열을 구하기 위해서 Math.max() 함수를 통해서 숫자가 클 때만 넣으면서 값을 구하면 끝!  결론 import java.util.Scanner;public class Main { public.. 더보기
반응형

티스토리툴바