본문 바로가기

전체 글682

백준 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.
백준 2759 자바 - 팬케이크 뒤집기 (BOJ 2759 JAVA) https://www.acmicpc.net/problem/2759 알고리즘 분류를 굳이 따지자면 constructive, ad-hoc, greedy 쪽일 것 같음. 애초에 답으로 가능한 경우 어떤 것이든 출력하면 되기도 하고, 이런 류의 문제를 풀기위한 well-known 스러운 풀이도 없다고 판단되므로 논리적 추론을 통해 이 문제만의 풀이과정을 만들어야 하는 종류의 문제이다. Brute force로 모든 경우를 보면 최대 O(30^30) 이라는 괴랄한 수가 나오므로 절대 무리.. 전 일단 가장 큰 수 부터 차례대로 맨 아래로 가야한다는 부분에 포인트를 맞추고, 그럼 위에서 k개를 뒤집는 방식으로 어떻게 가장 큰 수부터 차례대로 맨 아래로 내릴지 생각해봤다. 결론적으로 제 풀이는 다음과 같음. 가장 큰 .. 2021. 10. 7.
백준 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.
백준 22866 자바 - 탑 보기 (BOJ 22866 JAVA) https://www.acmicpc.net/problem/22866 풀이방법을 생각하기보다는 구현이 복잡한(==귀찮은) 문제였다. 일단 3가지로 나눠서 생각해봐야 하는데, 1. 각 건물에서 좌측으로 보이는 건물의 개수 2. 각 건물에서 우측으로 보이는 건물의 개수 3. 각 건물에서 가장 가까운 건물 번호 중 작은 번호 위와 같다. 일단 '각 건물에서 좌측으로 보이는 건물의 개수' 어떻게 구할지 생각해보자. 문제에서 제시된 예시를 예시로 들겠다. 3 7 1 6 3 5 1 7 에서 좌측부터 차례로 봐보자. 1번째 건물 : 3 이다. 현재 좌측으로 보이는건 없다. 뭐 일단 어딘가에 넣어둬보자. 2번째 건물 : 7 이다. 현재 좌측으로 보이는건 없다. (7보다 높아야 보임). 그 이후로는 모두 7에 막힐것이므로.. 2021. 10. 5.
백준 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.
백준 15989 자바 - 1, 2, 3 더하기 4 (BOJ 15989 JAVA) https://www.acmicpc.net/problem/15989 처음엔 무지성 DP 돌리면 될줄 알았는데, 수의 순서가 다른 것은 하나로 처리해야 한다. 무작정 dp 진행하며 모든 쌍을 확인하고, 그 중 겹치는 것을 확인하기엔 메모리가 부족해보인다. 풀이1. 2차원 DP https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15900/BOJ_15989_2D-DP.java 우선 서로 겹치는 쌍이 생기지 않도록 하려면 어떻게 해야할까? 각 n에서 더해지는 숫자에 제한을 두면 된다. 예를 들어 서로 겹쳐도 된다고 생각하고 n = 1~4 일 때 1,2,3의 덧셈으로 표현 가능한 경우를 보자. 1 : 1 2 : 2, 1+1 3 : 3, 1+1+1, 1+.. 2021. 10. 4.