반응형 분류 전체보기580 [동적계획법, 난이도 중] 백준 10844번 쉬운 계단 수 이 문제에서 신경써야 할 조건들이다. - 인접한 모든 자리수의 차이는 1이어야 한다. - 0으로 시작할 수 없다. - 정답을 10억으로 나눈 나머지를 출력해야 한다. 아마 이 문제의 정답율이 낮은 이유는 long long 자료형을 모르는 분들이 많아서 그런 것같다. int는 약 21억을 넘어가면 이상한 값이 나오는데 쓰레기 값이라고 하기도 한다. 이 때 int 대신 범위가 훨씬 더 넓은 long long을 써주면 된다. 계산할 때마다 10억으로 나눈다곤 하지만 이런 10개의 변수들을 모조리 합 한다면 21억을 넘을 경우는 충분히 생긴다. 아래 표에서 행은 맨오른쪽 끝의 자리수를 의미하며, 열은 숫자의 길이를 의미한다. 즉 DP[i][j] 값은 길이가 j이며 맨마지막에 i라는 자리수가 오는 경우의 수이다... 2020. 8. 20. [동적계획법, 난이도 중상] 백준 1912번 연속합 연속된 자릿값을 더해서 나올 수 있는 최댓값을 구하는 문제이다. 이 문제는 아주 특수한 경우 하나를 처리해줘야 한다. - 양수가 하나도 입력 되지 않았을 경우 이 경우에는 입력 값들의 최댓값이 정답이 된다. 이제, 나머지의 경우에 대해 DP를 수행해보자. 위 사진은 내 접근법에 대한 DP표이다. 먼저, 첫 번째 dp인덱스의 값은 첫 번째 입력값과 동일하다. 그리고 이후의 dp인덱스에 대해서는 다음과 같은 식을 이용했다. d[i]=max(0, d[i-1]+e[i]); #include #include using namespace std; int e[100001]; int d[100001]; int n, ans; int maxi=-1000; int main() { cin>>n; for(int i=1;i>e[i.. 2020. 8. 19. [동적계획법, 난이도 중] 백준 2156번 포도주 시식 백준 2579번 계단 오르기와 접근법이 비슷하다. https://kimcoder.tistory.com/54 [동적계획법, 난이도 중하] 백준 2579번 계단 오르기 이 문제의 주어진 조건을 요약하자면, 계단을 3칸 연속으로 밟을 수 없고 마지막 칸은 무조건 밟아야 한다는 것이다. 배열 save를 n번째 계단까지 올랐을 때 얻을 수 있는 최대 점수, 배열 floors을 � kimcoder.tistory.com 이 문제에서 주어진 조건은 1가지이다. - 연속되는 3자리의 포도주를 시식할 수 없다. 백준 2579번 계단 오르기 문제 조건과 차이점은 단 한 가지다. 마지막 자리를 꼭 선택할 필요가 없다는 것이다. 아래 사진에서 연한 노랑색은 이미 계산된 DP결과이고, 진한 노랑색은 시식할 수 있는 포도주 자리들.. 2020. 8. 19. [동적계획법, 난이도 중하] 백준 2193번 이친수 문제에 주어진 조건은 2가지이다. 1. 첫 번째 자리는 0이 될 수 없다. 2. 1이 두 번 연속으로 나타날 수 없다. 이 말은 n-1번째 자리가 0이라면 n번째 자리에는 0과1이 모두 올 수 있고 n-1번째 자리가 1이라면 n번째 자리에는 0만 올 수 있다는 것이다. 0은 첫 번째 자리 외엔 어느 자리에나 올 수 있으므로 n번째 자리가 0인 경우의 수는 n-1번째 자리가 0인 경우의 수와 n-1번재 자리가 1인 경우의 수의 합 1은 n-1번째 자리가 0인 경우에만 올 수 있으므로 n번째 자리가 1인 경우의 수는 n-1번째 자리가 0인 경우의 수 각 자리수의 두 경우의 수를 합한 결과가 이 문제의 답이다. 이를 표로 정리하면 이렇다. (예시로 n=7까지 작성) 예제 입력1) n=3인 경우 답은 2+1=3.. 2020. 8. 19. [동적계획법, 난이도 중하] 백준 2579번 계단 오르기 이 문제의 주어진 조건을 요약하자면, 계단을 3칸 연속으로 밟을 수 없고 마지막 칸은 무조건 밟아야 한다는 것이다. 배열 save를 n번째 계단까지 올랐을 때 얻을 수 있는 최대 점수, 배열 floors을 초기 입력된 계단 점수 배열이라 하면 이 문제의 점화식은 이렇게 된다. save[i] = maxs((save[i - 3] + floors[i - 1] + floors[i]), (save[i - 2] + floors[i])); 이다. 왜 이런 식이 나오는지는 아래 그림과 같이 설명하겠다. 위 그림에서 연한 노란색은 이미 DP로 처리한 부분이고 진한 노란색은 밟을 수 있는 계단들이다. 즉, 계단을 연속 3칸으로 밟는 것을 피하기 위해선 위와 같은 그림의 (O) 케이스가 되어야 하는데 3번째 케이스는 왜 계.. 2020. 8. 18. [동적계획법, 난이도 중] 백준 1149번 RGB거리 집에 색을 칠하는 조건 3가지가 명시되어있다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 간단하게 요약하자면 인접한 집끼리는 다른 색이어야 한다는 것이다. 즉 n번째 집까지 칠했을 때 n번째 집이 R이라면 비용의 최솟값은 n-1번째 집이 G색일경우의 총 비용의 최솟값과 n-1번째 집이 B색일경우의 총 비용의 최솟값중 더 작은 값. 그리고 n번째 집까지 칠했을 때 n번째 집이 G이라면 비용의 최솟값은 n-1번째 집이 R색일경우의 총 비용의 최솟값과 n-1번째 집이 B색일경우의 총 비용의 최솟값중 더 작은 값. 그리고 n번째 집까지 칠했을 때 n번째 집이 .. 2020. 8. 18. [동적계획법, 난이도 하] 백준 1932번 정수 삼각형 동적계획법을 처음 배우는 분들이 동적계획법에 대해 감을 익히기 적합한 난이도의 문제이다.이 문제보다 쉬운 DP문제는 포스팅하지 않을 것이다. 입력은 인덱스 0부터가 아닌 1부터 시작한다.DP는 대체로 이런 식으로 입력해야 편한 것 같다. 아래 표는 예제 입력1을 기준으로 작성했다. INPUT[1][1]값은 DP[1][1]에 그대로 넣어주고 (1년전에 본인이 짠 아래 소스코드에서는 DP배열이름을 root로 했다)인덱스 2부터 DP를 수행하여 DP[i-1][j-1]와 DP[i-1][j]중 최댓값과 INPUT[i][j]를 더해서 DP배열을 채워나가면 된다. 모든 과정을 마친 최종 DP 표이다. 맨 아래 5행의 요소들중 최댓값 30이 이 케이스의 답이 된다. #include #include using names.. 2020. 8. 18. [DFS, 난이도 중상] 백준 1937번 욕심쟁이 판다 알고리즘이 DP로 분류되어 있긴 하지만 DFS에 더 가깝다고 생각했고, 내 풀이법은 일반적인 DFS풀이와 전혀 다를 것이 없기 때문에 카테고리를 DFS로 했다. 이전값을 참고하여 현재 정보를 갱신한다는 점에선 동적계획법이기도한 문제이다. https://kimcoder.tistory.com/48 [동적계획법, 난이도 중상] 백준 1520번 내리막 길 이 문제는 동적계획법과 DFS를 동시에 적용해야 하는 문제이다. 백준 1890번 점프와 접근법은 비슷하다. https://kimcoder.tistory.com/47 [동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시� kimcoder.tistory.com 백준 1520번이 내리막길이라면, 이 문제는 오르막길이다. 판다는 자신이 있는 좌표.. 2020. 8. 17. [동적계획법, 난이도 중상] 백준 10942번 팰린드롬? 시간 제한은 0.5초이고 데이터범위는 100만인 시간 제한이 매우 빡센 문제이다. 이 때문에 문제의 난이도 평가를 중상으로 할지 상으로 할지 고민했다. 본인은 동적계획법으로 이렇게 접근했다. 예) 문제 입력에서 수열의 크기 N=12 그리고 칠판에 적은 수를 1 2 2 1 2 1 2 2 1 2 2 2로 가정했을 때의 dp표이다. 홍준이가 한 질문 최대 100만개는 이 표를 참고하여 대답해줄 것이다. 행은 팰린드롬의 길이, 열은 홍준이가 칠판에 적은 숫자를 나열한 것이다. 이 표는 팰린드롬의 중심을 기준으로 했을 때 길이 별 팰린드롬 여부를 나타낸 것이다. 예를 들어 7행 5열에서 "o"로 표시되어 있는데 흥준이가 칠판에 적은 숫자들중 5번째인 "2"를 중심으로 했을 때 연속 수의 길이가 7인 숫자열은 팰린.. 2020. 8. 17. 이전 1 ··· 57 58 59 60 61 62 63 ··· 65 다음
