[백준 / C언어] 14501번: 퇴사

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 난이도: solved.ac 실버 3 실버 3치고 어려웠다... 다른 분들은 맨 마지막 날부터 거꾸로 계산하던데 나는 정직하게 첫 날부터 계산했다ㅋ (거꾸로 계산하는 센스는 dp 문제를 많이 풀어봐야 얻을 수 있나보다...) 내 풀이를 예제 입력 1을 통해 설명해보겠다 예제 입력 1 7 3 10 5 20 1 10 1 20 2 15 4 40 2 200 우선 크기가 N + 1인 1차원 dp 배열을 만든다 (나는 N의 범위를 1000까지로 잘못 봐서 메모리를 적게 하려고 동적할당했는데, 정적할당으로 해도 괜찮을 것 같다) 일단 1일차. 1일..

• format_list_bulleted PS/백준
• · 2023. 5. 15.
• textsms

[백준 / C언어] 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 Knapsack Problem으로 유명한 문제다 이 알고리즘에 대해 설명해보려고 했는데 너무 길어지고 글로 설명 못하겠어서 포기했다...ㅠ 대신 내가 참고했던 유튜브의 링크를 첨부할 테니 이 알고리즘에 대해 이해가 되지 않는 분이 본다면 분명 도움이 될 것이다 https://youtu.be/nLmhmB6NzcM https://you..

• format_list_bulleted PS/백준
• · 2023. 5. 14.
• textsms

[백준 / C언어] 11051번: 이항 계수 2 (파스칼의 삼각형)

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 난이도: solved.ac 실버 2 앞에서 다룬 문제 (이항 계수 1)의 확장판(?)이다 N과 K의 범위가 1000까지로 늘어났다 이 문제는 파스칼의 삼각형을 이용하면 쉽게 풀 수 있다 파스칼의 삼각형의 공식을 dp 점화식으로 만드는 건데, 이에 대해 설명해 보겠다 우선 파스칼의 삼각형은 아래와 같다 이 파스칼의 삼각형은 아래의 이항계수로부터 만들어진 건데 각 수는 한 칸 왼쪽 위와 한 칸 오른쪽 위의 수의 합이라는 특징이 있다 이를 수식으로 나타내면 다음과 같다 근..

• format_list_bulleted PS/백준
• · 2023. 5. 12.
• textsms

[백준 / C언어] 11050번: 이항 계수 1

https://www.acmicpc.net/problem/11050 난이도: solved.ac 브론즈 1 이 문제는 다이나믹 프로그래밍을 이용해서도 풀 수 있지만, 그건 이다음에 업로드할 11051번 문제(실버 2)에서 서술하겠다 (수의 범위만 더 커지고 똑같은 문제임) 브론즈 문제 답게 쉬운 방식으로 풀어보자 조합 공식을 그대로 코드로 옮기는 것이다 [조합 공식] 맨 오른쪽에 있는 변은 조금 복잡해 보이지만 사실 간단하다 N부터 시작해 1씩 작은 수를 K개 만큼 곱한 것을 K!로 나눈 것이다 (예시) 아래는 이를 그대로 코드로 옮긴 것이다 #define _CRT_SECURE_NO_WARNINGS #include int main() { int N, K, com = 1, i; scanf("%d %d", &..

• format_list_bulleted PS/백준
• · 2023. 5. 11.
• textsms

[백준 / C언어] 10844번: 쉬운 계단 수

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 난이도: solved.ac 실버 1 dp 문제다 점화식을 세우기 위해 N = 1일 때부터 차례로 해보자 N = 1일 때, 1, 2, 3, 4, 5, 6, 7, 8, 9로 길이가 1인 쉬운 계단 수는 9개가 된다 N = 2일 때, 10 12 21​ 23 32 34 43 45 54 56 65 67 76 78 87 89 98 로 17개가 되는데, 눈치채셨을까? 길이가 N인 i로 끝나는 쉬운 계단 수는 길이가 N - 1인 i - 1로 끝나는 쉬운 계단 수와 i + 1로 끝나는 쉬운 계단 수에 i를 붙여 만들어진다 그림..

• format_list_bulleted PS/백준
• · 2023. 5. 9.
• textsms

[백준] 11053번: 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 난이도: solved.ac 실버 2 LIS(Longest Increasing Subsequence)문제다. 나는 DP를 이용해 풀었다. #define _CRT_SECURE_NO_WARNINGS #include #define MAXLEN 1000 #define max(a,b) ((a)>(b)?(a):(b)) int mai..

• format_list_bulleted PS/백준
• · 2023. 4. 29.
• textsms