dp 썸네일형 리스트형 [프로그래머스] (2024 KAKAO WINTER INTERNSHIP) 산 모양 타일링 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 경우의 수를 10007(큰 소수)로 나누어 return해야하는 점에서 단순 구현으로 해결할 수 없고 이전 값에서 다음 값을 아는 DP를 사용해 해결하는 문제입니다. 점화식 형태로 풀어내기 위해서 어떤 형태들을 만들 수 있는지 파악하고 다음 값에 영향을 주는 요소를 알아야 합니다. 기본 모형인 큰 정삼각형을 덮는 방식은 4가지 입니다. 1. 정삼각형 타일 2. 왼쪽 정삼각형 + 중간 정.. 더보기 [백준] 1937 욕심쟁이 판다 / 자바(Java) 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 해설 판다가 돌아다닐 수 있는 가장 많은 칸을 찾는 문제입니다. 출발점이 정해져 있지 않으니 모든 점을 출발점으로 경로를 확인해야 합니다. 지나온 값의 총 합의 기반으로 경로를 정하지 않기 때문에 2차원 dp배열을 통해 연산량을 줄입니다. dp[i][j]는 (i,j) 위치를 지날 때 가장 많이 이동한 횟수 dfs를 통해 지도의 모든 위치에서 주변 4방을 탐색 후 자신보다 큰 위치(.. 더보기 [백준] 2565 전깃줄 / 자바(Java) 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 해설 어느 전기줄들을 제거해야 교차되는 전기줄이 없을까 확인하는 문제입니다. 풀이방식을 어떻게 잡을지 몰라 고민했지만 DP를 사용해 해결하였습니다. DP배열의 의미는 dp[i] => i번째 까지에서 교차되지 않으려면 설치하는 최소 전기줄 수 로 하였습니다. 제거가 아닌 설치를 기준으로 생각해서 좀 더 문제를 해석하기 쉽도록 되었습니다. 같은 위치에는 2개이상의 전기줄이 연결될 수 없으므로 입력 값을.. 더보기 [백준] 1309 동물원 / 자바(Java) 문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 해설 dfs와 같은 탐색으로 해결하기에는 N의 길이가 너무 길다(답을 9901로 나눈 나머지를 출력하라는 부분도 값이 크게 되리라는 예상이 된다) 따라서 DP를 사용해 이전의 경우의 수에서 가능한 가능성을 구하는 점화식의 형태로 문제를 해결한다. arr[i][j]에서 i 는 사자우리의 세로번째의 수, j는 0~2까지 각각 사자가 들어가지 않는 경우, 왼쪽칸에 들어간경우, 오른쪽 칸에 들어간 경우를 나타내어 arr[i][j]는 i번째에 각 가능성이 될 경우의 수가 들어가게 된다. 사자우리는 바로 이전 번째에서만 영향을 받아 a.. 더보기 [프로그래머스] 숫자 변환하기 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/154538# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 특정 자연수 x에서 y로 변환하는데 필요한 최소 연산 횟수를 구하는 문제입니다. bruteforce로 해결하려 한다면 각 연산요소 3가지(+n, *2, *3)을 매번 계산해 주어야 해서 x가 1이고 y가 1,000,000인 경우 3^1000000정도가 필요합니다. 하지만 DP를 사용하면 3*1000000정도로 깔끔한 풀이가 가능해 집니다. 목표는 최소 연산 횟수를 구하는 것이기 때문.. 더보기 [백준] 14501 퇴사 / 자바(Java) 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 해설 상담이 매일 잡혀있고, 앞의 상담 여부가 뒤의 상담가능 여부를 정하기 때문에 각 일자별 최대 금액을 구하는 dp를 이용하여 문제를 해결하였다. dp[i]를 해당 일자의 최대 금액이라 한다면 점화식을 이와 같이 세울 수 있다 dp[i + t[i]] = max(dp[i + t[i]] , dp[i] + p[i]) 현재 i에서 상담일(t[i])를 더한 날의 최대 금액에서 오늘 일을 한 경우와 본래 있던 경우 중 최대값을 현재 최대값으로 넣어준다. 이때 dp배열의 크기는 N을 벗어나지 않으므로 조건을 추가해준다 if( i + t[i.. 더보기 이전 1 다음
