[백준 14225] 부분수열의 합, C++
https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 � www.acmicpc.net 본 문제는 주어진 수열의 부분수열을 구하고 구한 부분수열의 합을 구하는 문제다. 문제를 해결하기 위해 2가지의 과정이 필요하다. 1. 모든 부분수열의 합을 구한다. 2. 1.에서 구만 합을 저장한다. 위의 과정마다 각각 2가지 방법이 떠올랐다. 1.을 해결하기 위해서는 비트 마스크를 이용하여 모든 경우의 수를 찾는 방법과 재귀..
2020. 9. 27.
[백준 2309] 일곱 난쟁이, c++
www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 진짜 일곱 난쟁이를 찾는 문제 총 9명중 7명을 고르는 문제다. 문제의 조건 중 일곱 난쟁이의 키의 합이 100이라고 한다. 따라서 7명을 고르는 모든 경우의 수를 확인하면서 7명의 합이 100일 때 오름차순으로 출력하고 종료를 하면 된다. 문제 해결을 위해 next_permutation()을 이용하였다. { 0, 0, 1, 1, 1, 1, 1, 1, 1 }으로 만들 수 있는 모든 경우의 수를 만들고 1일 때 해당 위치..
2020. 9. 8.
[백준 15685] 드래곤 커브, C++
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 본 문제는 문제도 잘 이해되지 않고, 접근하기가 어려워 검색을 통해 힌트를 얻었다. 문제의 핵심은 다음과 같다. 첫 방향이 0이고 3세대인 경우는 (0), (0, 1), (0, 1, 2, 1), (0, 1, 2, 1, 2, 3, 2, 1)과 같은 규칙으로 드래곤 커브를 만들 수 있다. (0, 1)를 i번이라 하면 i+1번은 (i번 째) + (i번을 1씩 증가하고 뒤집는..
2020. 5. 16.