Algorithm/백준 (22) 썸네일형 리스트형 [백준] 16500번: 문자열 판별 https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다. www.acmicpc.net 한참동안이나 붙들고 있었던 문제..ㅠㅠ 처음에는 정말 간단하게 아래와 같이 입력이 주어졌을 때 softwarecontest 2 software contest 문자열 S에서 단어를 하나씩 지워가면서 문자열을 모두 지울 수 있는지를 검사하면 된다고 생각했었는데 틀린 접근법이었다. 반례는 soft, s.. [백준] 12865번: 평범한 배낭 https://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 첨에 내가 푼 접근법이 완전 틀려서 ㅠㅠ 결국 인터넷에 검색해서 다른분들 해설을 보고서야 해결했다. DP문제 중 매우 유명한 배낭 문제로, 각각의 무게와 가치가 주어진 N개의 물건이 있을 때, 무게가 K가 넘지 않도록 물건들을 배낭에 넣어서 최대 가치를 구하는 문제이다. 접근법은 .. [백준] 11051번: 이항 계수 2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수를 구하는 문제. 간단하게 생각해서 1~N까지의 팩토리얼을 구해서 배열에 저장하면 되지 않을까 생각했지만, 1000!은 long long의 표현 범위조차 아득히 넘어버린다. 따라서 nCr = n-1Cr-1 + n-1Cr 이라는 조합 공식을 이용해야 한다. include using namespace std; int dp[1001][1001]; int main(void) { int N; int K; cin >> N >> K; for (int i = 0; i [백준] 11570번: 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net DP로 풀 수 있는 간단한 문제 1~N자리 오르막수의 끝나는 숫자(0~9)를 배열에 저장해놓고 DP로 풀면 된다. 다만 각 자릿수별로 배열을 몽땅 선언해 버리기가 싫어서 현재 자릿수와 이전 자릿수를 저장하는 동적 배열 curr, prev를 선언했다. 각 자.. [백준] 11052번: 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제가 길지만 한마리로 얘기하면, 1~N장의 카드 셋과, 각각의 가격이 주어졌을 때 N장의 카드를 구입하기 위해 지불할 수 있는 최대 가격을 구하는 문제이다. 역시나 DP를 이용해서 풀 수 있다. N장의 카드의 최대 가격은 dp[N-i] + price[i](i = 1 to N)의 최대값이다. 이 점을 이용해서 잘 구현하면 됨! #include #include using namespace std; int .. [백준] 1699번: 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net DP를 이용해서 푸는 문제. 풀이의 핵심은 N의 제곱수 항의 최소개수를 구하고 싶다면, N에서 N보다 작거나 같은 제곱수를 뺀 값을 구.. 이전 1 2 3 다음
