BOJ 백준Dynamic Programming 검색 결과

해당 글 15건

백준 12852 - 1로 만들기 2

출처 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 고려사항 동적 프로그래밍을 활용하면, 가작 작은 연산 수는 쉽게 구할 수 있다. 그 경로를 추적하는 것은 생각보다 어려웠다... 근데 그냥 똑같은 길이의 배열하나 더 만들어서 더 최소값이 나와서, v의 값이 갱신 될 때, 해당 값이 어떤 수에서 왔는지 path배열에 기록해주고 1을 만날 때 까지 쫙 뽑아주면 되는 것이 었다.. #include #include using namespace std; int memo[1000001]; int path[1000001]; int dp(int num){ ..
BOJ 백준/Dynamic Programming 4년 전

백준 09252 - LCS 2

출처 : https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 고려사항 동적 프로그래밍 LCS 알고리즘을 응용하여 제일 긴 부분 문자열의 요소들을 뽑아내는 문제. lcs 를 재귀로 풀 수도 있고( 09251 - LCS ), 이 문제처럼 bottom -> top 으로 반복문으로도 풀 수 있다. 재귀는 top -> down 이다! 현재 조사중인 str1 의 인덱스 y 와 str2의 인덱스 x 들의 문자가 ..
BOJ 백준/Dynamic Programming 4년 전

백준 02407 - 조합

출처 : https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 고려사항 long long 을 넘어가는 수 출력. ( 문자열로 다루는 것도 생각해보았지만 너무 복잡, 실패...다른 해결법을 참조하였다..) 조합은 이항 계수 공식 사용. ( 수학을 못하는 문돌이 출신은 이번에 처음 알았다..ㅎㅎ ) 100C50 이 대략 10^29 ~ 10^30 사이의 수이다. 10^15 를 maxValue 로 정해놓고, 이 값 이상이면, carry 배열+1 출력은 carry > 0 일 시에, 먼저 carry 출력 후 combi 출력. carry 가 존재하고, combi 가 10^13 ..
BOJ 백준/Dynamic Programming 4년 전

백준 11660 - 구간 합 구하기 5

출처 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 고려사항 입출력 시간 줄이기...cstdio printf scanf 를 쓰거나, sync_with_false 를 쓰는 습관을 들여야하는데... (사실 여지껏 응시한 코테에서는 위와 같은 제한 사항은 없다...) x줄에서 각각의 y 좌표까지의 구간합 정보를 memo 에 저장한다. 41 - 45 라인의 방식으로 정답 도출. #include using..
BOJ 백준/Dynamic Programming 4년 전

백준 02156 - 포도주 시식

출처 : https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 고려사항 - i 번째 포도주를 안마신다면, i-1번째 포도주를 안마심(0), 마셨는데 연속 1잔째임(1), 마셨는데 연속 2잔째임(2) 를 나타내는 memo[i-1][0~2] 중 최대값을 계산해야 함. - 재귀로 구현했더니 몇몇 테스트 케이스에서 답이 안구해짐... 아마도 아까 언급한, 안 마셨을 때의 값이 이전 인덱스의 모든 값중 최대값을 구해야하는데, 재귀로 할 경우 반복문으로 구하는 ..
BOJ 백준/Dynamic Programming 4년 전

백준 10844 - 쉬운 계단 수

출처 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 고려사항 - memo[len][num] 은 len 길이의 수 중 끝이 num 으로 끝나는 수의 개수. - 끝 수가 0과 9일 때는 각각 길이가 1 짧은 수들 중 끝이 1, 8 로 끝나는 수의 개수이며 이 밖에는 길이가 1 짧은 수들 중 끝이 자신과 1 차이나는 수로 끝나는 수의 개수들을 더한다. - memo[len][num] = memo[len-1][num+1] + memo[len-1][num-1] - 계산 후 % 10억 - 스위치문을 썼는데 모든 끝 자리수를 탐방하니 0~9까지 반복문을 활용하면 더욱..
BOJ 백준/Dynamic Programming 4년 전

백준 01463 - 1로 만들기

출처 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 고려사항 - 2와 3중 나눗셈이 가능하다면 dp 연산. - -1 연산은 항상! #include #include using namespace std; int n; int memo[1000001]; int dp(int num){ int &v = memo[num]; int nextV = 1000000; if(num == 1){ v = 0; return v; }else if(num == 2){ v = 1; return v; }else if(num == 3){ v = 1; return v; } if(v != 0..
BOJ 백준/Dynamic Programming 4년 전

백준 02565 - 전깃줄

출처 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 고려사항 - lis 알고리즘 활용 - 로 벡터에 넣은 후, first 기준으로 정렬 => 0 - n-1 까지의 인덱스를 지닌 v.second 를 하나의 수열이라 여김. - 최대 증가 수열 길이를 구하고 n-ans 를 해줌. #include #include #include using namespace std; vector v; int n, ans = -1; int memo[101]; int mai..
BOJ 백준/Dynamic Programming 4년 전