JJ_blog

이 문제는 어렵다기보다 아이디어 차이인 것 같다. 문제를 해결한 방법으로 DP를 사용하였다. 일반적인 Dp방법으로 1. (앞 → 뒤) 방향으로 dpI를 담는다. 2. (뒤 → 앞) 방향으로 dpD를 담는다. 그 이후 두 dp들을 더한다. 더한 후 가장 값이 큰 요소를 찾은 다음 1을 뺀다. 소름 돋게 간단하다. □ 소스 코드 void bye11054(){ int n; scanf("%d",&n); vector array; vector dpI(n); vector dpD(n); for(int i=0;i

수열 문제를 풀다 보니 4,5번까지 오게 됐다! 14002, 14003은 앞선 문제들(12015, 12738)과 다르게 부분 수열의 최대 길이뿐만 아니라 부분 수열도 출력을 해야 한다. 물론 Dp 방식으로 문제를 풀면 14002는 해결할 수 있지만 14003은 범위 때문에 시간초과로 해결하지 못한다. 이번 문제에서도 아래 문제에서 풀 듯이 이진탐색을 섞어서 풀었다. [백준] 12015, 12738 가장 긴 증가하는 부분 수열 2,3 11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000..

11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000,000,000 ~ 1,000,000,000 [백준] 11053 가장 긴 증가하는 부분 수열 DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf( hj39-develop.tistory.com 11053을 공부할때 Dp로 푸는 방법과 이진 탐색을 이용해서 푸는 방법을 공부 했었다..

이번 문제는 11053과 다르게 가장 긴 수열의 길이를 찾는 게 아닌 증가하는 수열들 중에서 가장 큰 합을 가지는 부분 수열을 찾는 문제이다. 11053에서 찾은 새로운 방법(이진 탐색)으로 합을 찾아보려고 했지만.. 할 수 없는 건지 실력이 부족한 건지 풀 수가 없었다. ㅠㅠ 더 공부한 후에 다시 도전해 봐야지 그래서 결국 DP를 이용하여 문제를 해결했다. 11053에서 DP를 이용한 방법과 아주 유사하다. 앞선 문제에서는 dp 배열에 길이를 저장했다면 이번 문제에서는 dp 배열에 원소의 합을 저장해 주면 된다. □ 소스코드 void best11055(){ int n; scanf("%d",&n); int array[1001] = {0}; int dp[1001] = {0}; for(int i=1;i

DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf("%d",&n); int dp[1001] = {0}; int array[1001] = {0}; for(int i=1;i

이름은 쉬운데 문제는 전혀 쉽지가 않다.. 계단 형식으로 된 숫자들을 찾는 건데 DP 문제라 규칙을 찾는 것이 가장 중요하다!! 하지만 규칙을 찾으려고 자리 수별로 숫자도 세보고,, 자리 수의 첫 번째 자리, 마지막 자리만 떼서 규칙을 찾아봤지만 이런거로는 규칙을 찾을 수 없었다.. ㅠㅠ 도움을 받은 블로그..! https://yabmoons.tistory.com/22 [ 백준 10844 ] 쉬운 계단 수 (C++) 백준의 쉬운계단수(10844) 문제이다.( 문제 바로가기 ) [ 문제를 다시 푸는 과정에서 보다 구체적인 설명을 해 놓은 글을 다시 포스팅 하였습니다. 아래의 글을 읽더라도 무관하지만 , 보다 구체적 yabmoons.tistory.com 해당 블로그 해설을 보고 이해 한 후에 문제를 풀었다...

DP 문제들은 문제를 풀 수록 어렵네; 점화식 찾기가 너무 어려워ㅓㅓ 최대값을 구하는 방법으로 입력받은 값 array[i]과 이전까지의 값(dp[i-1])을 비교하여 큰 값을 dp[i]에 저장하면 된다. #include using namespace std; void yeun1912(){ int n; scanf("%d",&n); int array[100'001]; int dp[100'001]; for(int i=0;i

9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net /* num = 1 MARK: => 1 num = 2 MARK: => 1 num = 3 MARK: => 1 num = 4 MARK: => 2, P(1) + P(2) num = 5 MARK: => 2, P(2) + P(3) num = 6 MARK: => 3, P(3) + P(4) num = 7 MARK: => 4, P(4) + P(5) num = 8 MARK: => 5, P(5) + P(6) num = 9 MARK: => 7, P(6) + P(7) num = 10 MA..

해당 문제는 백준[1654] 랜선 자르기와 매우 흡사한 문제이다. 재귀함수를 이용하면 코드가 간결해져서 쉽지만 시간초과가 날까 봐 재귀함수를 사용하지 못하겠다ㅜ #include int findMaxBranches(vector &arr, int M, int start, int end){ int result = 0; while(start= M){ result = mid; start = mid + 1; } else{ end = mid - 1; } } return result; } void cutTree(){ int N,M; scanf("%d%d",&N,&M); vector arr; for(int i=0;i

해당 문제는 이진 탐색을 살짝 응용한 문제인데 전체적인 코드를 짜기는 쉬웠지만.. 특수한 케이스들이 존재해서 해당 반례를 찾느라 푸는 시간이 많이 늦어졌다..ㅠ #include long long findcuttingSize(vector &arr,long long N, long long start, long long end){ long long result = 0; while(start= N){ result = mid; start = mid + 1; } else{ end = mid - 1; } } return result; } void cuttingLan(){ long long K,N; cin>>K>>N; vector arr; long long max = 0; for(int i=0;i