알고리즘 문제풀이/백준134 [백준 15779] Zigzag www.acmicpc.net/problem/15779 15779번: Zigzag 어떤 수열에서, 연속된 3개의 수를 보았을 때, 그 수가 단조증가 수열이거나, 단조감소 수열인 경우가 없으면 이 수열을 "지그재그 수열" 이라고 말한다. 좀 더 정확하게는, 길이 N의 수열 A가 모 www.acmicpc.net n이 5000까지이므로 브루트 포스 수열 안에 모든 숫자를 3개씩 확인해본다. 만약 지그재그 수열에 해당한다면 1씩 길이를 늘려주고 max값을 업데이트해준다. 지그재그 수열이 깨지면 다시 최소 지그재그 수열길이인 2부터 시작한다. #include #include using namespace std; int arr[5000]; int main(void) { int n; scanf("%d", &n); fo.. 2020. 11. 23. [백준 2193] 이친수 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net dp 사용 문제 규칙에 따라 11은 올 수 없고 0으로 시작하는 숫자도 올 수 없다. n = 1일 경우 1 n = 2일 경우 10 n = 3일 경우 101 100 n = 4일 경우 1010 1000 1001 이전 단계에서 0과 1의 개수에 따라 다음 단계에서 만들 수 있는 숫자의 수가 정해지는 걸 확인할 수 있다. 그래서 zero를 저장하는 dp와 one을 저장하는 dp를 따로 만들어줬다. one[i.. 2020. 11. 14. [백준 2293] 동전1 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net dp를 사용하는데 점화식 세우는 데에 애먹었다. ㅠㅠ 주어진 동전을 기준으로 경우의 수를 세는 것이 문제의 핵심이다. 접근: 주어진 예시에서 1 2 5의 동전이 주어졌다고 했다. 1의 동전을 사용하면 k=10에 도달하기 까지 경우의 수가 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 모두 1이 될 것이다. 그 다음 2의 동전을 사용해보자. 1의 경우 2보다 작으니까 2의 동전을 사용해서.. 2020. 11. 14. [백준 16987] 계란으로 계란치기 www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net n의 범위가 1부터 8까지이기 때문에 브루트 포스 & 백트래킹을 하면 풀리는 문제이다. 주의할 점: hand== n인 기저조건까지 도달하기 위해 모든 조건에서 backtracking함수를 실행시켜야 한다는 것이다. ' ++괜히 경우의 수를 출력한다고 했다가 너무 많은 경우의 수라서 무한 루프 도는 것처럼 보였다... #include #include #define MAX 8 //n=8이기 때문에 다.. 2020. 11. 12. 이전 1 ··· 28 29 30 31 32 33 34 다음