백준 15779 자바 - ZigZag (BOJ 15779 JAVA)
https://www.acmicpc.net/problem/15779 i번째 데이터에 대해, i-2, i-1, i 번째 데이터를 살펴보며 단조증가 수열이거나 단조감소 수열일 경우 arr[i] = 0을 기입했고, 지그재그 수열일 경우 1을 기입함.(13line) 그럼 예를들어서 문제에 제시된 2번째 예시 (1,3,4,2,5)의 경우 제가 짠 로직으로는 arr = [0, 0, 0, 1, 1] 와 같이 기입됨. 근데 이 때 1이 연속된 갯수가 결국 지그재그 수열의 길이이므로, 13line처럼 이전값+1을 해주면 연속된 길이도 한꺼번에 구할 수 있음. 최종적으로 arr 배열에 있는 가장 큰 수가 가장 긴 지그재그 수열의 길이이므로 max값을 찾아주고 (19line) 거기에 2를 더해준게 답임. (+2를 해준 것은..
2021. 10. 8.
백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA)
https://www.acmicpc.net/problem/15993 f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면, f(n) = f(n-1) + f(n-2) + f(n-3) 이다. 왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 + f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다. 위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다. 그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자. a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀..
2021. 10. 7.
백준 12931 자바 - 두 배 더하기 (BOJ 12931 JAVA)
https://www.acmicpc.net/problem/12931 우선 처음으로 생각할 부분이, 만약 시작지점인 0,0,0,... 에서 시작해서 제시된 B 배열을 찾아가려면 결국 모든 경우를 봐야한다. 매번 B 배열과 비교하며 최소 연산 횟수를 찾게 짜는건 사실상 무리라고 본다. 그럼 반대로 B 배열에서 0,0,0,...을 찾아가는걸 생각해보자. 제시된 연산은 각각에대해 1을 더하는 것과 전체에 대해 2를 곱하는 것이므로, 반대로 B배열에서 0,0,0,... 을 찾아가기 위해서는 각 배열에 대해 1을 빼는 연산과, 전체에 대해 2로 나누는 과정을 거쳐야 한다. 그럼 N=1일 때 조차도 무조건 2로 나누는 것이 이득인 것을 쉽게 알 수 있다. (더 적은 연산으로 차이를 더 많이 낼 수 있음) 최종적으로 ..
2021. 10. 5.
