본문 바로가기

백준

[백준] 2293번 : 동전1 ( 파이썬, 쉬운 설명, 코린이 버전 ) *이 문제가 너무 어려웠던 코린이는 오세요* 디피 자식 ..... 풀어도 풀어도 어려운 너란 유형 .... 자존감 떨어뜨리는 유형 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 디피 문제를 많이 풀어보고 있지만, 풀이를 들었을 때는 솔직히 이해가 갑니다. 하지만, 아직 까지는 스스로 풀어볼 때, 디피를 적용하는 데에는 제 경험이 딸리나 봅니다. 어쩌겠습니까? 못풀면 그 풀이에 대한 해설을 제대로 익히고, 이해하고. 다음에 못풀어도, 또 경험을 쌓다보면, 디피를 조금씩 더 잘 할 수 있지 않을까요? 우선.. 더보기
[백준] 12865번: 평범한 배낭( 파이썬, 쉬운 설명, 코린이 버전 ) *비범한 배낭 주의 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 매우 매우 매우 매우 어려운 문제였습니다. 저한테는. 문제 제목이 매우 역설적으로 자괴감 느끼게 하고 ㅋㅋㅋ 누가 이게 디피의 전형적인 문제라고 해서 더 자괴감을 느꼈습니다. 하지만, 자괴감을 느끼는 것도 이제 익숙해서, 저항이 생겨가네요. 많은 시간을 들여서, 결국 이해를 하고 여러분에게 전달드립니다. < 코린이를 위한 쉽게 설명한 핵심 아이디.. 더보기
[쉬운 설명] 백준 1912번 연속합(파이썬, dp) www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 사실 이 문제는 여느 동적프로그래밍 문제에 비해서 너무 너무 쉬운 편이에요. 그렇다고 해도, 제 딴의 풀이를 공유해볼게요. 베이스 아이디어 1. 주어진 정수 리스트에 대한 리스트를 만든다( 흔히 말하는 dp list ) 2. dp의 의미는 이 인덱스 입장에서 취할 수 있는 최대입니다. * 여기가 중요한데요. * 만약, 이 번 인덱스에 주어진 수에 의해서, 이전 인덱스까지의 dp를 감소하게 한다면, 그 이전 인덱스까지의 결.. 더보기

티스토리툴바