본문 바로가기

DP5

[Java] 백준 2096번 내려가기 문제 952hi의 접근방법 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 접근방법 문제를 읽자마자 백준에서 RGB거리라는 문제가 생각이 났다. 크게 다를게 없어서 바로 dp 다이나믹 프로그래밍 알고리즘을 사용해서 문제를 풀었다. 간단하게 1번열은 직전 1,2 열 2번열은 직전 1,2,3열 3번열은 직전 2,3열의 영향이 다음으로 합쳐지는 방식이기 때문에 dp를 사용했고 3차원배열을 사용해 최소 최대를 구해줬다. 2. 느낀점 다 풀고 3차원배열안쓰면 더 빠를거 같은 느낌이 들긴했.. 2022. 5. 12.
[Java] 백준 12865 평범한 배낭 952hi의 접근방법 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 접근방법 배열을 여러개 사용하고 싶지 않다는 생각이 들어서 하나로 해결할 수 있는 방법을 고민했고 초기 1차원 배열을 무게만큼 생성하고 1~N개 모두 0으로 초기화한후 물건 1~M까지 차례로 끝 인덱스 부터 접근해 넣었을때 가치와 넣고 남은 무게의 가치 즉 직전 회전의 가치를 활용해 계산함 ex) 물건2 무게 4 총 배낭 무게.. 2022. 4. 18.
[Java] 백준 11054 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 문제바로가기 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 접근방법 1. dp기반의 LIS 알고리즘을 사용해야겠다 생각함 2. 처음에는 문제를 잘못이해해서 좌우로 같은 거리만큼 떨어진것이 바이토닉 수열인줄알아서 우측방향 LIS 왼쪽방향 LIS을 통해 각 인덱스별로 값이 같은거를 출력해주려고했음 3. 손으로 숫자 적어보면서 그냥 좌우로 길기만 하면된다고 판단해서 같은게 아닌 더해서 가장 큰값을 출력해주면 됐음 2. 실수 1. ->진행방향는 괜찮았지만 2022. 4. 11.
[Java] 백준 1003 피보나치 함수 https://www.acmicpc.net/problem/1003 문제바로가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 접근방법 1. 재귀함수로 0 1일때 리턴해주고 숫자세서 출력해줘야겠다. 2. 시간초과-> 0.25초라 재귀적으로는 풀지못하고 dp로 풀어야겠다고 생각함. 3. 0,1일때 각각 출력해줘야하므로 dp테이블 2개를 따로 선언해 각각 더해주고 출력해주기로 생각함. 2. 실수 및 느낀점 1. 문제를 꼼꼼히 읽지않고 바로 내 방식으로 품 만약 테케를 제공해주지 않거나 채점결과를 알려주지 않는 테스트라면 분명 좋지 않을 것이라고 생각함. 2. dp로 풀어도 좀더 효율적으로 짤 수 있지않을.. 2022. 4. 11.
[JAVA] 17404 RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 접근방법 1) 문제를 읽고 바로 dp라고 생각이 들었다 1행이 2행에 영향이 있고 ... N행까지 영향을 주니까 2) 첫번째집을 R G B 각각 선택했을때 N행에서 만약 첫행 선택한 색이 R을 선택했다면 마지막행 R은 최솟값 선택에서 제외 3) 아래 그림을 그리면서 아이디어 획득함 이전 행에서 현재 색을 제외하고 최소값을 구해준다. 예를 들면 현재 레드2행 이라면 1행.. 2022. 3. 27.

티스토리툴바