Problem Solving1212 [백준] 2217 로프 - Greedy / Java • 문제 링크 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class .. 2022. 5. 6. [백준] 1890 점프 - Dynamic Programming / Java • 문제 링크 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net • 풀이 과정 이 문제의 경우 게임판과 메모이제이션할 배열을 따로 입력받지 않아도 풀이가 가능하다. 우선 n + 1 * n + 1 크기의 dp 배열을 생성하고 dp[1][1] = 1 로 시작점을 초기화한다. 반복문에서 dp[i][j] 가 0일 경우, 해당 위치로 이동 가능한 경우의 수가 1개 이상이 아님을 의미하므로 처리하지 않는다. 입력받은 dist 값은 현재 위치에서 이동 가능한 거리이며 우측, 하단 방향으로 그 거리만큼 이동했을 때.. 2022. 5. 5. [백준] 15486 퇴사 2 - Dynamic Programming / Java • 문제 링크 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net • 풀이 과정 아래 링크는 n의 범위가 다르지만 내용은 같은 문제로 완전 탐색으로 풀이했고 이번엔 DP로 풀이했다. [백준] 14501 퇴사 - Brute Force / Java • 문제 링크 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net • 풀이 과정 해당 문제는 재귀를 활용하여 완전 탐색(Brute Force) 으로 해결하거나 동적 계획법(DP graycod.. 2022. 5. 4. [백준] 14501 퇴사 - Brute Force / Java • 문제 링크 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net • 풀이 과정 해당 문제는 재귀를 활용하여 완전 탐색(Brute Force) 으로 해결하거나 동적 계획법(DP) 으로도 해결 가능하다. 아래 링크에서 내용은 같지만 N의 범위가 넓은 "퇴사 2" 는 DP로 해결했고 이 문제는 완전 탐색으로 풀이했다. [백준] 15486 퇴사 2 - DP /Java • 문제 링크 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ P graycode.tistory.com 우선 총 상담.. 2022. 5. 4. [백준] 11399 ATM - Greedy / Java • 문제 링크 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net • 풀이 과정 앞 사람의 인출시간이 짧을수록 뒤의 인원이 부담해야 할 시간이 줄어드므로 소요시간을 오름차순으로 정렬한다. 이 후 인원 당 소요된 시간을 앞 사람이 소요한 시간까지 포함해 누적한 값으로 temp 변수에 구하고 각각 cnt 변수에 모두 더해 필요한 시간의 합의 최솟값을 구한다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import ja.. 2022. 5. 2. [백준] 11047 동전 0 - Greedy / Java • 문제 링크 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net • 풀이 과정 문제 중 동전의 가치가 일정한 값으로써 Ai가 Ai-1의 배수인 조건에 의해 그리디로 해결 가능하다. 동전은 n 종류, 가치의 합이 될 값은 k로 입력받고 각 동전의 가치가 오름차순으로 List에 저장된다. 우선 동전의 가치가 큰 순서대로 비교하기 위해 입력받은 List를 Collections.reverseOrder() 로 내림차순 정렬한다. 저장된 각 값을 k와 연산하는.. 2022. 5. 1. 이전 1 ··· 199 200 201 202 다음
