문제 이름 - 날짜 0뽀 - 성능
- - [문제 링크]()
- - 공개한 1등 기록:
- - 추정 시간 복잡도:
- - 문제 핵심
- - 해결 과정
- - 다른 코드 감상 및 배울 점
- - 궁금하다! 더 공부하고 싶다!
- - 하고 싶은 말
- - [노션 링크]() - 다른 코드 및 틀린 코드 확인
피보나치 함수 - 23/11/17 0.5뽀 - 23284KB 264ms
1, 2, 3 더하기 - 23/11/15 0.7뽀 - 23284KB 264ms
- 문제 링크
- 공개한 1등 기록: 14000KB 116ms
- 문제 핵심
- 1, 2, 3 숫자를 이용하기에 N이 늘어나며 생기는 규칙을 발견할 수 있는가.
- 해결 과정
- 냅다 5까지 경우의 수 적으면서 이전 배열을 어떻게 이용할 수 있을까.
- (i-1)번째 +1, (i-2)번째 +2, (i-3)번째 +3 진행 시 빠짐없이 1, 2, 3 이용한 모든 조합 완성
- 이 경우, 3번째까지는 i-3 이용하기 어려워서 어느 순간이든 넣어주기 위해 N+2 크기의 배열 생성 (dp[0]은 0이 맞다고 판단)
- 1, 2, 3 더하기 3을 먼저 봤는데, 처음에 규칙이 잘 찾아지지 않았음.. → 깨끗한 새 종이에 이전 것에서 늘어나는 걸 1:1 매핑하면서 찾아냄!
- 다른 코드 감상 및 배울 점
- n과 같아질 때까지 dfs 진행
- dfs지만, dp로 구한 것보다 빠를 수 있다..!
- 트리로 뻗어나가는 dfs 재귀로 풀어 보기, 이때 내가 원하는 대로 정확히 동작하는지 확인까지!
- 궁금하다! 더 공부하고 싶다!
- dfs가 dp보다 빠르기도 한가?
- 경우의 수가 적으면 하드 코딩을 하는 게 더 나을 수도 있는 걸까?
- 하고 싶은 말
- 1,2,3 더하기 3 불과 얼마 전만 해도 풀지 못했는데! 역시 한눈에 보이는 종이에 풀어야 하는 건가? 아침에 지금 정신이 맑은가? 아주 뿌듯^_^! 진짜..0.5뽀모 만에 발견하고, 후다닥 짜서 해결.. 왕뿌듯…~!~!
- 노션 링크 - 다른 코드 및 틀린 코드 확인
연속합 - 23/11/14 2.5뽀 - 23284KB 264ms
- 공개한 1등 기록: 14908KB 152ms
- 문제 핵심
- 연속된 숫자의 가장 큰 합 구하기 -> 입력 받으며 sum, max 바로 구하기 -> sum을 초기화하는 적절한 지점 찾기 -> sum < 0인 경우 0으로 초기화
- 어려웠던 부분 해결
- 음수가 허용되기 때문에, max 초기값은 min_value로 설정해야 함.
- 배열 0부터 끝까지 쭉 돌면서 max 찾음. -> 시간 초과
- left, right ptr 이용
- right idx를 늘려가며 sum 구하고 max와 비교해 max 업데이트
- 이때 sum < 0 되면 left=right+1, right=+2, sum = left
- 풀다 보니 ptr 구현 X -> 입력 받으면서 바로 cur 값을 sum에 더하며 0 미만, max 비교
- sum=cur 시 음수 이후 양수부터 더하기 불가
- sum=0으로 초기화 후 max를 바로 비교해서 -1이 max으로 들어가지 않음.
- 순위 코드 분석 후 배운 점
- dp, sum<0인 경우 그 다음에서 거르는 방식 → 이전 수까지의 합에 현재 숫자를 더한 값과 현재 숫자를 비교해 큰 값을 취하기
- read를 받아 변수에 저장하며 동시에 파라미터로 활용하기
- max 대신 sumList를 sort해서 마지막 idx 출력
- 보충이 필요한 지식
- 코드 로직은 크게 다르지 않은데, 시간과 메모리 차이는 어디서 나는 걸까? read를 직접 구현한 게 둘 다에 영향을 미치는 건가?
- max 를 직접 구현하는 게 Math.max를 쓰는 것보다 나은 건가? 아니면 등호의 차이가 큰 건가?
- 구현: return a > b ? a : b; / max return a ≥ b ? a : b;
- 하고 싶은 말
- 생각보다 금세 풀어서 왕뿌듯..!!!! 그동안 dp 풀며…. 그래도 쪼끔은 성장했나보다!!!!!! 짱이다…!!!!!!! 문제 풀이도 조금 생각하니 떠올릴 수 있었고, 조건도 조금 미숙했지만, 반례 찾으면서 어떤 게 문제인지 확인 후 고쳤다,,,~!~!~!~!
- 역시 다양한 상황을 가정할 수 있도록 좀 더 연마해 보기!
- 노션 링크
(Hint) 민균이의 계략 - 23/11/13 3뽀 - 15128KB 148ms
- 공개한 1등 기록: 14252KB 128ms
- 문제 핵심
- 상자 넣기와 동일, LIS
- 이전 숫자와 현재 숫자를 비교하고, 이전 digit dp의 최댓값에 +1
- 이전에 조건문에서 최댓값 비교해 주는 방식 이용
- 상자 넣기와 동일, LIS
- 어려웠던 부분 해결
- 조건문 비교 후 업데이트하는 값이 dp[i]여야 dp[i]에 최댓값이 입력됨 -> 조건문 안에서 dp[i]가 아닌 temp로 업데이트 후 모든 for문을 돈 후 temp를 넣어주면, 당연히 마지막 조건을 통과했던 그 temp가 들어가서 이전 최댓값 dp[j]로 업데이트되는 걸 보장하지 못함.
- max에서 N 범위 설정
- 순위 코드 분석 후 배운 점
- String[] temp = br.readLine().split(" ")로 입력 받기
- high idx 반환하는 binSearch, ptr 구현해 구하기
- for j=i 시작, 뒤랑 비교하며. dp[i] == dp[j], 뒤가 더 큰 경우, dp[j]++
- 보충이 필요한 지식
- dp[i] == dp[j] 이 조건이 필요한 이유
- Arrays.binarySearch(a, t)이 어떤 걸 반환하는지 확인하고, 이용해 보기
- LIS의 길이를 구하는 3가지 알고리즘 → 이진 탐색으로 푸는 법 공부하기!
- 하고 싶은 말
- 처음 dp의 최댓값이 아니었다는 걸 찾지 못해... 답 통과 후 지금 보니 오류가 보인다 허허...
- … 이진탐색으로 푸는 것도 배우고, 이렇게 푸는 것도 좀 더 익힐 필요성은 있는 듯.
- max도 그 안에서 효율적으로 구하는 걸 배우자.
- 노션 링크
이친수 - 23/11/12 0.5뽀 - 14216KB 124ms
- 공개한 1등 기록: 14124KB 120ms
- 문제 핵심
- 이전 digit에서 가능한 0, 1 개수에 따라 좌우됨
- 0인 경우 1, 0 둘 다 사용 가능
- 1인 경우 이후엔 0만 올 수 있음.
- 이전 digit에서 가능한 0, 1 개수에 따라 좌우됨
- 어려웠던 부분 해결
- long 판별이 어렵다... 어떻게 long인 걸 딱 알지? -> 우선 바로 90 찍어보고 범위 벗어난 것 확인 후 수정
- 순위 코드 분석 후 배운 점
- 피보나치….. 01타일과 동일한.. 문제...
- D[i]=(D[i-1]-count)*2+count;
- t, o. l 변수 세 개로 해결
- 피보나치 블로그 설명
- 보충이 필요한 지식
- static 변수, 메서드를 사용하는 것과 main 내에서 하는 . 게차이가 나나?
- call by value
- 변수의 지역변수와 전역변수의 시간차이에 대해서.. - 캐시 힛 등
- 하고 싶은 말
- 바로 피보나치인 걸 인식하지 못해서 자료형이 어려웠지만, 그래도 바로 적절하게 출력해 보고 알아챌 정도로는 성장한 거 같아서 기쁘다^_^~!
- 노션 링크
(Hint) 쉬운 계단 수 - 23/11/11 3.5뽀 - 17732KB 212ms
- 공개한 1등 기록: 14148KB 120ms
- 문제 핵심
- 이전 수에서 가지치기를 어떻게 해서 현재 수로 넘어오는지 구하고, 전체 수 더해주기.
- 어려웠던 부분 해결
- 두 번째까지만 세어 보고, 0, 9인 경우에 대해 납작하게 (dp[i - 1] * 2 - 1) 이렇게만 생각함. -> 블로그 참고
- arr 정답 배열에 담을 때 += 사용해 자료형 범위 넘어가며 틀림.
- 블로그에서 이전 수에서 현재 수로 넘어올 때 선 그은 걸 보고 관계를 이렇게 맺어서 해당 수를 모두 더하면 되는 구나! -> 0~9까지 하드 코딩
- 0에서 가지치기가 되는 건지 헷갈려서 한 번 더 틀리고, 맨 처음만 안 되는 걸 다시 확인함.
- 순위 코드 분석 후 배운 점
- for 내에서 if로 0,9 거르고, 마지막 dp만 sum 구해서 출력
- Arrays.toString 사용해서 print하면 배열 내 요소 출력
- 0일때, 9일때를 나눠서 for문 내 if 두 개로 각 j-1, j+1인 경우를 한 번에 처리 가능
- for(j = 0; j++ < 10;) 사용
- N+2하는 것처럼 앞 뒤에 공간 주고, 처음부터 끝까지 같은 점화식 사용
- dp 전체 배열 X, 이전과 이후 저장하는 배열만 생성해 사용
- 보충이 필요한 지식
- mod 계산에 대해 추후 공부해 보기
- int, long 최대 허용치 외우기…
- topdwon, bottomup 구현
- dp 내의 배열 숫자가 커질수록 내가 생각한 양상이 아니었음… 잘 생각해 보기.
- 하고 싶은 말
- 11/4에 못 풀고, 오늘 도전, 힌트를 보고 풀어냈다.
- 좀 이해 못한 것도 있지만, 그래도 오랜만에 다른 사람 코드에서 재밌는 부분을 찾았다 ㅎㅅㅎ~!
- 블로그 글처럼.. 생각하는 게 dp 핵심같은 기분!
- 노션 링크
상자넣기 - 23/11/10 1.5뽀 - 14644KB 152ms
- 공개한 1등 기록: 14256KB 124ms
- 문제 핵심
- 현재 순서보다 앞선 순서에서 작은 수를 찾고, 그 수에 저장된 (그 수보다 작은 수의 개수의 최댓값)이 가장 큰 수 +1
- 어려웠던 부분 해결
- dp에 넣을 (가장 큰 dp 값 가진) 작은 수를 찾기 -> 0~i까지 for를 돌리며 이전 값과 비교
- 순위 코드 분석 후 배운 점
- 이진 탐색 사용해 dp 배열에서 유의미한 가장 긴 부분 수열 길이 구하기
- D[j]>=D[i] && S[i]>S[j] 로 하면 이전 dp[j]에서 가장 큰 값에 +1하게 됨.
- 보충이 필요한 지식
- LIS, 블로그 이진 탐색 사용 설명
- 이진 탐색에서 어떤 걸 구하고자 하는 건지 확인
- low는 next와 같거나 가장 가까운 작은 수? high는 ?
- 이진 탐색에서 어떤 걸 구하고자 하는 건지 확인
- LIS, 블로그 이진 탐색 사용 설명
- ~칭찬~
- 그래도.. ㅎㅅㅎ 가장 긴 감소하는 수열…. 열심히 떠올려서 풀었다 뿌듯.
퇴사 - 23/11/9 3뽀 - 14236KB 132ms
- 공개한 1등 기록: 14184KB 120ms
- 문제 핵심
- 시간을 idx로 후에 완료될 일 값과 비교하기
- 어려웠던 부분 해결
- dp[i][j]:
- i: 시간의 흐름,
- j: 수락한 일을 해당 일까지 완료했을 때의 받을 돈
- 1<=j<=5: 일을 수행 완료하기까지의 일수,
- j=0: 해당일까지 받을 돈의 최댓값
- 입력: 각 1~5일차 뒤의 dp 배열의 해당하는 j번째에 저장
- dp[i][0]: n일 전의 0번째 + i(당일)의 n번째 중 (총 5일 비교) 가장 금액이 큰 값을 i(당일) 0에 저장
- idx error -> -5까지 있어서 배열 크기 +5
- dp[i][j]:
- 순위 코드 분석 후 배운 점
- ... 거의 이해를 못함 .....
- 보충이 필요한 지식
- Max 값을 여러 개 비교할 수 있는 방법
- 하고 싶은 말
- 와.. 큰일났다.. 진짜로 모르겠다........ 뭐지..? 다들 점화식을 어떻게 다 저렇게 세운 거지?
01타일 - 23/11/08 0.5뽀 - 22296KB 148ms
- 공개한 1등 기록: 14196KB 128ms
- 문제 핵심
- 피보나치 수열
- 어려웠던 부분 해결
- for 문의 종료 조건 수 +1로 배열 크기 설정해야 idx error X
- 순위 코드 분석 후 배운 점
- 저장하지 않고, a, b, result 변수만 업데이트, 1,2인 경우 따로 처리 필요.
- 보충이 필요한 지식
- 이게 어떻게 가능하지?
- 짝수: dpn = (n / 2) ((n / 2) + 2 (n / 2 - 1)) % MOD;
- 홀수: dpn = (((n + 1) / 2) ((n + 1) / 2) % MOD + ((n - 1) / 2) ((n - 1) / 2) % MOD) % MOD;
- 이게 어떻게 가능하지?
- 하고 싶은 말
- 풀었던 문제랑 비슷한 유형 나오니까 슥삭..! 이래서….. 문제를 많이 풀어보는구나! 요즘 의기소침했는데, 뭔가….. 좀 자신감이 생기는 기분? ㅋㅋㅋ
(Hint) Four Squares - 23/11/7 4뽀 - 14572KB 148ms
- 공개한 1등 기록: 14272KB 132ms
- 문제 핵심
- 제곱수인 경우 dp[i - j * j]이 dp[0]으로 출력돼 dp[i]=1이 됨.
- j가 1부터 j*j<=i(i와 같아지는 제곱수)까지 돎 => 이전 수까지 dp에 저장되어 있어서 저장된 배열로 이용 가능
- 0부터 j * j < i까지로 하면 j=0일 때 dp[i]에 저장된 수가 0이라 계속 0만 출력됨.
- 나머지수(=해당 수 - 제곱수)를 구하는 최소 수는 이미 dp에 있어서 어떤 제곱수를 뺀 나머지 수를 이용하는 게 더 최소를 보장하는지를 j for문에서 비교
- 어려웠던 부분 해결
- dp 이해 -> print로 확인
- 순위 코드 분석 후 배운 점
- 재귀로 dp 풀기
- 각 for에서 1,2,3,4 return
- 보충이 필요한 지식
- 예시에서 만족하는 제곱수를 뽑은 것처럼 만족하는 제곱수를 전부 출력하려면 어떤 조건을 추가하면 가능하지?
- 하고 싶은 말
- dp를 더 열심히 풀자..!
(Hint) RGB거리 - 23/11/6 2뽀 - 14600KB 132ms
- 공개한 1등 기록: 14140KB 120ms
- 문제 핵심
- 이전 조건에 따른 최솟값 구하기
- 각 r,g,b 각각에서 시작해 겹치지 않게 min으로 dp 진행
- 어려웠던 부분 해결
- 백트래킹으로 시도했으나 풀리지 않아 dp 힌트 및 코드 확인..
- 순위 코드 분석 후 배운 점
- 입력 받을 때부터 dp 가능!
- red, green, blue 상수로 이용
- 나머지 이용해 행 별로 메모이 제이션 이용 / 두 행으로 비교
- stream으로 min 출력
- 보충이 필요한 지식
- dp 공부
- 메모이제이션 적절하게 활용하는 법
- 백트래킹으로 푼다면?
- 하고 싶은 말
- ...... dp를 더 공부하자.
(Hint*3) 가장 긴 감소하는 부분 수열 - 23/10/24 3뽀 - 14396KB 148ms
- 공개한 1등 기록: 14108KB 124ms
- 문제 핵심
- 블로그 참고
- if 세 번째 수인 경우 앞선 두 번째까지의 수 중 큰 수가 존재하고, 해당 digit의 dp+1이 현재 digit의 현재 dp보다 크면 then
- 현재 digit의 현재 dp에 해당 digit dp +1
dp[i] = dp[j] + 1;
- 현재 digit의 현재 dp에 해당 digit dp +1
- i번째마다 현재 개수와 dp[i]의 개수 중 더 큰 값 구해서 cnt 저장
어려웠던 부분 해결
- 유니크한 수 구해서 수열로 만들기 set 사용 -> 예제에서 dp 1 1 2 2 2 3 출력까지 도출
- 조건식 어려워서 hint 확인 -> 이전 수 전체와의 비교, 그 중 저장된 dp 값이 높은 수+1
순위 코드 분석 후 배운 점
- 이분 탐색으로도.. 풀 수 있다...
보충이 필요한 지식
- 이분 탐색으로 푸는 법..!
~칭찬~
- 음.. 열심히 배웠다!
1로 만들기 - 23/10/21 2.5뽀 - 18288KB 148ms
공개한 1등 기록: 14292KB 120ms
- 내 기록: Scanner 사용 시 21676KB 232ms, BufferedReader 사용 시 18288KB 148ms
문제 핵심
- memoization을 이용해 dp[N]을 구하는 것이 핵심!
- dp[i] = (i-1)번째, (i/3)번째, (i/2)번째 중 min으로 구하는 것이 핵심
- 비교 시 i%6, i%3, i%2가 0에 해당 하는 경우에 min 비교
- 도달하는 방법이 3가지만 있다고 알려준.. 친절한 문제였음..!
어려웠던 부분 해결
- 무작정 3, 2로 나눠지는 경우에 대해서만 나누려고 함.
- 마지막에 1을 만들기 위해 점화식을 세움. -> 이게 오답 원인.
- 1~N까지 순차적으로 각 값의 min을 구하고 이용하는 방식으로 변경 -> 해결
- 무작정 3, 2로 나눠지는 경우에 대해서만 나누려고 함.
순위 코드 분석 후 배운 점
- 재귀 이용! 그냥 N/2, N/3 숫자 비교하는데 각각 횟수를 N%2, N%3을 더해도 가능
보충이 필요한 지식
- 각각 횟수를 N%2, N%3을 더해서 비교하는 게 min을 왜 보장하지..?
- 로직이 같은데, 시간 차이 이유? 재귀가 더 빠른가? 어떤 차이지?
~칭찬~
- 생각보다 오래 걸리고, 시간 제한 마감에 떠올라서 시간을 더 쓰긴 했지만 그래도 dp를 잘 떠올린 것 같다! 다음에는 카테고리 보지 않고도 잘 풀어낼 수 있으면 좋겠다!
(Hint) 평범한 배낭 - 23/10/18 0뽀 - 성능
- 공개한 1등 기록:
- 추정 시간 복잡도:
- 문제 핵심
- 어려웠던 부분 해결
- 순위 코드 분석 후 배운 점
- 보충이 필요한 지식
- ~칭찬~
2xn 타일링 2 - 23/10/18 1.5뽀 - 14328KB 128ms
- 공개한 1등 기록: 14180KB 124ms
- 문제 핵심
- i-2, i-1에서 중복되는 부분 셈하기
- (i-2) 모음에 각각 ||, =, ㅁ을 더해 주면 2*i을 채울 수 있고, (i-2)모음 *3 개.
- (i-1) 모음에 |을 더해 주면 이 또한 2*i을 채울 수 있음. (i-1) 모음 - (i-2) 모음 개.
- (i-2) 모음을 기본으로 하고, 여기에 없는 걸 (i-1)에서 더해줌.
- 기본으로 삼은 게 (i-2)이고, (i-1) 모음의 앞 부분이 (2*i-2) 모양과 같은 걸 제외해야 하기 때문.
- i-2, i-1에서 중복되는 부분 셈하기
- 어려웠던 부분 해결
- 정해진 마지막을 기준으로 그 전 단계 경우의 수 고민하기
- 순위 코드 분석 후 배운 점
- (입력은 1부터라고 명시되어 있지만) 0인 경우도 1로 초기화해 점화식 2부터 진행
- br.readline() 한 글자면 그대로 사용해도 됨.
- 보충이 필요한 지식
- 문제에서 10007 수로 설정한 이유?
- ~칭찬~
- 지난 번에 배운 대로 생각해서 해냈다! 비교적 불필요한 코드는 넣지 않은 것 같다!
(Hint) 구간 합 구하기 5 - 23/10/17 3뽀 - 118280KB 844ms
- 공개한 1등 기록: 26792KB 312ms
문제 핵심
(1,1)부터 해당 위치까지의 구간합을 각 배열에 구하고, 요구하는 구간만의 합을 도출하기
//(1,1)부터 해당 위치까지의 합 sumArr[i][j - 1] + sumArr[i - 1][j] - sumArr[i - 1][j - 1] + Integer.parseInt(st.nextToken());//최종 구간 합 int prefixSum = sumArr[x2][y2] - sumArr[x2][y1-1] - sumArr[x1-1][y2] + sumArr[x1-1][y1-1];- 꼭 그림 확인하고, 부분 -> 전체인 부분 고려하기!
- 어디서 어떻게 점화식을 도출할 건지 고민
- 어려웠던 부분 해결
- 시간 초과
- 시간 초과날 걸 알았지만, 떠오르지 않아 for 진행 -> 역시나 시간 초과라 힌트 확인 후 각 합을 구해 배열에 넣기 성공
- 구간 합 구하기 오류
- 그림으로 확인 안 하고, (x2, y2) - (x1-1, y1-1) 진행해 틀림 -> 다른 힌트 그림 보고 구획 나눠 답 도출
- 시간 초과
- 순위 코드 분석 후 배운 점
- x1, y1 받을 때 로직에서 사용하는 값은 실질적으로 -1이라 처음부터 그렇게 저장
- 상위권 대부분 read() 구현해 사용.
- 보충이 필요한 지식
- read() 등 구현 및 메서드 분리
- ~칭찬~
- 시간 초과 날 걸 알았지만, 답이라도 구해 보자는 마음으로! 다음에는 지금 배운 걸 열심히 기억하고 적용하기!
- 어제 합을 생각했던 만큼 조금 더 시간을 들였어도 좋았겠지만, 시간 내에 풀지 못한 건 맞으니까. 빠르게 잘 결정했다!
이동하기 - 23/10/16 4.5뽀 - 77880KB 532ms
- 공개한 1등 기록: 23036KB 204ms
- 문제 핵심
- 대각선은 생각할 필요 없음.
- 대각선으로 한 번 오는 것보다 오른쪽/아래쪽을 한 번 거쳐 오는 게 사탕을 더 많이 담을 수 있음.
- idx 고려
- 대각선은 생각할 필요 없음.
- 어려웠던 부분 해결
- 처음 발상 -> 불확실해 단념
- 최대 합을 구하는 거라 대각선은 의미 X
- 이동 수: N+M-2
- dp[이동 수] = 갈 수 있는 지역의 합
- 이동 시마다 머물렀던 셀 제외 행/열의 합을 빼 주기.
- 정답 발상
- 위쪽/왼쪽 중 더 많은 사탕을 가진 쪽의 경로를 택하고 현재 사탕 합치기
dpRes[i][j] = Math.max(dpRes[i - 1][j], dpRes[i][j - 1]) + candy[i][j];
- 위쪽/왼쪽 중 더 많은 사탕을 가진 쪽의 경로를 택하고 현재 사탕 합치기
- 구현 시 고친 점
- r=1, c=1인 경우를 각각 구하고, r=2, c=2인 경우를 따로 구하면 예시 코드나 반례는 돌아가는데, 백준 1%에서 틀렸다고 나옴.
- 여기서 힌트 확인, 따로 구하지 않고, idx를 1로 설정해서 그냥 1부터 N까지 점화식 구하니 정답.
- 동기님이 알아챈 사실: dpRes 배열 이름을 candy라고 잘못 적어서 오류였음...!.. 고치고 돌리니 첫 코드도 맞았음. -> ... 답이 다 나와도 내가 의도한 대로 동작하는지 확인 위해 디버깅 한번 돌려 보기..! 컴파일러가 잡지 못하는 인간오류를... 발견해야 한다...
- 처음 발상 -> 불확실해 단념
- 순위 코드 분석 후 배운 점
- r, c 1일 때는 그냥 for 한 개로 합쳐도 무방, 필요한 조건인지 꼭 생각해 보기.
- 입력 받으면서 동시에 dp 구하는 것도 가능
- 보충이 필요한 지식
- BFS가 아닌 DP인 이유? 어떤 상황에서 어떤 알고리즘이 더 적절할지 선택하는 법
- 점화식의 기준을 잘 파악하기
- ~칭찬~
- 점화식 발상을 해낸 것이 장하다! 비록... 배열명을 틀려서 힌트를 봤지만, dp에 한 걸음 더 다가간 기분~.~
(Hint) 2xn 타일링 - 23/10/15 2뽀 - 14324KB 128ms
- 공개한 1등 기록: 14204KB 124ms
- 문제 핵심
- 마지막 수 기준으로 그 직전 경우의 수를 구하고, 점화식으로 표현하기! - 경우의 수 조건을 잘 나누는 게 핵심!
- 혹은 일정한 규칙으로 조합 구해서 각 수를 구하면 피보나치 수열 등장!
- 짝수, 홀수 규칙
- 홀수(2n-1): n개 더하기 - C(2n-1,0)+C(2n-1-1,1)+...+C(2n-1-n+1,n-1)
- 짝수(2n): (2n-n+1==n될 때까지) n+1개 더하기 - C(2n,0)+C(2n-1,1)+...+C(2n-n+1,n)
- 각 수열에 나머지 연산을 해도 결과는 같음!
- 수 = (10007*몫+나머지)로 표현한다면 (수+수+수+…+수)%10007에서 나머지%10007만 따로 빼서 계산이 가능
- 즉, 전체 수에 나머지 연산을 하는 건 각 수의 나머지 연산을 더한 것과 같음.
- 어려웠던 부분 해결, 배운점
- 피보나치 수열 구했는데, 틀렸습니다! -> N이 일정 숫자 이상이면 출력값 범위를 넘어감.
- 이전에는 출력 시에만 %10007했는데, 각 수열에 %10007 진행, 이 과정에서 이렇게 해도 되는지 힌트 봄.
- 항상 범위 고민하기~!
- 순위 코드 분석 후 배운 점
- 1,2인 경우 적절한 조건으로 코드 반복 X
- dp[1]=1 이후 if(n≥2)로 dp[2] 저장
- N+2개로 초기화해서 1,2를 아예 더하고 시작
- 0,1 등 연산할 필요 없는 특정 조건이면 그냥 바로 print하고 return!
- 보충이 필요한 지식
- 조합을 이런 조건 하에 모두 더하는 게 원래 피보나치를 유도하는 공식 같은 건지? 어떻게 이게 피보나치가 나오는 건지? 아니면 조합을 구하는 자체에도 점화식을 유도할 수 있는지?
- 결국 마지막은 기준으로 생각하고, 마지막에 도달하는 직전 경우의 수를 나누고, 그걸 점화식으로 표현하는 게 핵심.
- ~칭찬~
- 차근차근 하나씩 계산해서 조합까지 규칙 발견하고, 어떻게 해야 하지 고민하다 혹시나 다 더했는데, 피보나치가..!!! 진짜 기뻤고, 끝까지 계산해서 규칙을 발견해야 하는구나.. .생각했다!!! 크~! -> 블로그를 보니 내가 구한 건 맞기야 하겠지만 우연이었겠구나 생각했다 하하.
- 나머지 연산.. 저렇게 해도 되는지 아리까리해서 간단히 검증도 해서 이해하고! 짱짱!!!
1~9까지 계산
1: 1 = 1
2: 1+1 = 2
3: 1+2 = 3
4: 1+3+1 = 5
5: 1+4+3 = 8
6: 1+5+6+1 = 13
7: 1+6+10+4 = 21
8: 1+7+15+10+1 = 34
9: 1+8+21+20+5 = 55
2: 1+1 = 2
3: 1+2 = 3
4: 1+3+1 = 5
5: 1+4+3 = 8
6: 1+5+6+1 = 13
7: 1+6+10+4 = 21
8: 1+7+15+10+1 = 34
9: 1+8+21+20+5 = 55
(Hint) 계단 오르기 - 23/10/14 3.5뽀 - 14132KB 124ms
- 공개한 1등 기록: 13992KB 116ms
- 문제 핵심
- 점화식!!!!!
- 마지막 확정된 계단을 기준으로 경우의 수를 찾아내기
- dp[i]=dp[i-3]+stairs[i-1]+stairs[i]
- dp[i]=dp[i-2])+stairs[i]
- 어려웠던 부분 해결
- 초반에 생각한 방식 -> 생각 후 검증 어려워 바로 힌트 확인
- 가장 수가 커야 하니 많이 가는 게 좋다는 걸 전제
- 3개 중 OUT이 없으면 3개 중 1개는 무조건 건너뛰고, 그 직전에 OUT이었으니 2,3번째 숫자 중 작은 숫자 OUT
- OUT이 있다면 다음 3개로 넘어감.
- idx 오류
- 점화식 처리 중 dp 배열과 stairs 배열의 idx 1,2 예외 처리 오류 -> 디버깅으로 확인 후 수정
- 점화식이 i-3까지 있어서 1부터 시작해야 1,2만 예외 처리로 가능.
- 순위 코드 분석 후 배운 점
- 점화식이라서인지 입력을 받으면서 바로 dp를 돌려 dp 저장 및 최종 출력 가능
- 보충이 필요한 지식
- 점화식의 기준, 검증 시 확인해야 할 부분
- idx를 0부터 설정할 때의 점화식 조건은?
- 확인한 순위권, 숏코딩은 전부 점화식 같음 -> 점화식 떠올리기 연습만이 살 길.
- ~칭찬~
- 고민을 한 시간 정도 하고, 떠오른 생각을 검증할 수 없을 것 같아 과감하게! 정답을 확인한 것
- 처음 접해 보는 문제라 생각해 본 후 정답 input을 넣고 output을 내는 게 더 효율적
- 와중에 힌트만 얻으려고 파이썬 코드를 봤지만, 정말 잘 읽혀서 의미는 없었다...