[백준 / C언어] 15649번: N과 M (1)

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 난이도: solved.ac 실버 3 1부터 N까지의 숫자에서 M개를 중복없이 골라 각기 다른 순서로 섞어 나열하는 순열을 만들어내는 문제다 이는 DFS를 활용한 백트래킹으로 해결할 수 있다 우선 출력할 숫자는 배열 arr에 담아두었고 배열 used에는 각 인덱스에 해당하는 숫자가 배열 arr에 저장되었다면 1, 저장되지 않았다면 0을 담았다 그리고 idx가 M이 되면 배열 arr에 저장했던 수를..

• format_list_bulleted PS/백준
• · 2023. 5. 13.
• 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언어] 1654번: 랜선 자르기

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 난이도: solved.ac 실버 2 이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)을 활용하면 O(log n)의 시간 복잡도로 풀 수 있는 문제다 N개의 랜선을 입력받을 때 배열에 저장하는 동시에 최대값을 찾아 그 최댓값을 right라고 두고 left는 길이가 1인 가상의 랜선으로 두었다 그리고 while문 안에서 mid = (l..

• format_list_bulleted PS/백준
• · 2023. 5. 10.
• 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

[백준 / C언어] 1920번: 수 찾기

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 난이도: solved.ac 실버 4 정렬과 이분 탐색(Binary Search)을 활용한 문제다 나는 A라는 배열에 M개의 수를 저장한 후 qsort를 돌려주었고 B라는 배열에 M개의 수를 저장한 후 Binary Search 함수를 이용해 값이 있으면 1, 값이 없으면 0을 리턴하도록 만들었다 만약 나처럼 compare 함수를 이렇게 썼다면 아래의 ..

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