[백준] 10844번 - 쉬운 계단 수 (한줄평) 생각보다 빨리 아이디어가 떠올라 쉽게 풀 수 있었던 문제! 2차원으로 접근해야한다는 것을 깨달으면 쉽게 풀 수 있다. 한번쯤 복습해보면 좋을 것 같은 문제 풀이 시간: 20분 이내 1) 문제 해결 아이디어 인접한 모든 자리의 차이가 1인 수를 계단수라고 한다. (단, 0으로 시작하는 수는 계단수가 아니다) 1이상 100이하의 자연수 n이 주어질 때, 길이가 n인 계단 수의 총 개수를 구하는 문제다. 길이가 n인 계단 수의 마지막 숫자는 0 ~ 9 사이의 수로 10가지 경우가 있다. 길이가 n, 마지막 숫자가 j인 계단 수의 개수 = 길이가 (n - 1)인 계단수 중 j - 1, j + 1 로 끝나는 계단수의 개수의 합이다. 그러므로 길이가 n인 계단수의 ..
[백준] 1463번 - 1로 만들기 (한줄평) 전에 풀었던 문제와 유사하지만 생각보다 시간이 좀 걸렸던 문제! 유사 문제: https://hseungyeon.tistory.com/285 [다이나믹 프로그래밍] ▲ 문제1 - 1로 만들기(217p) [이코테] 문제1 - 1로 만들기(217p) (한줄평) 평소였으면 최소값을 구하는 문제니 BFS로 해결 했을테지만 전형적인 다이나믹 프로그래밍 문제! 추후 복습이 꼭 필요한 문제 풀이 시간: 40분 이내 1) hseungyeon.tistory.com 풀이 시간: 20분 이내 1) 문제 해결 아이디어 정수 X(1
[백준] 2579번 - 계단 오르기 (한줄평) 조건때문에 계속 헷갈려서 생각보다 어려웠던 문제! 코드는 단순하지만 복습이 필요하다!! 풀이 시간: 40분 이내 1) 문제 해결 아이디어 다음 조건을 만족하면서 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. i는 무조건 O이므로 (i - 1)은 O 혹은 X가 될 수 있다. 1. ~ OXOO일 때 - (i -1)이 O이면 (i -2)는 무조건 X여야한다. 조건2에서 연..
[백준] 1932번 - 정수 삼각형https://www.acmicpc.net/problem/1932 (한줄평) 익숙한 dp 문제라 쉽게 풀 수 있었던 문제! 풀이 시간: 10분 이내 유사 문제: 1149 https://hseungyeon.tistory.com/298 [다이나믹 프로그래밍] 1149번 - RGB거리 [백준] 1149번 - RGB거리 (한줄평) 아이디어를 쉽게 떠올릴 수 있었던 문제! 효율적인 코드를 짤 수 있게 고민해볼 수 있는 문제였다 이 문제는 집의 수 n(2
[백준] 1149번 - RGB거리 (한줄평) 아이디어를 쉽게 떠올릴 수 있었던 문제! 효율적인 코드를 짤 수 있게 고민해볼 수 있는 문제였다 이 문제는 집의 수 n(2
[백준] 9461번 - 파도반 수열 (한줄평) 손으로 직접 쓰면서 규칙을 알아냈던 문제! 하나씩 다 해보다보면 규칙이 보기도한다는 것을 꺠닫게 되었다! 풀이 시간: 20분 이내 1) 문제 해결 아이디어 첫 정삼각형의 변의 길이는 1이고 나선 모양으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 떄, 그 변에 길이가 k인 정삼각형을 추가한다. 이러한 행위를 반복 했을 때 나선에 있는 정삼각형의 변의 길이 p(n)을 구하는 문제다. 이 문제는 직접 하나하나 써보면서 규칙을 찾을 수 있는 문제였다. Q. dp테이블을 전연변수로 선언하고 입력을 받기전에 100까지 계산을 하는 이유는? 사실 n을 입력받고 나서 p(n)값을 계산해도 상관 없지만 테스트 케이스가 2이상일 경우에 기록된 값에 ..
[백준] 1904번 - 01타일 (한줄평) 아이디어는 쉽게 떠올렸으나 오류를 고치는데 시간이 걸렸던 문제! 나중에 다시 한 번 풀어봐야할 것 같다 (풀이1) 틀린 코드 풀이 시간: 20분 이내 1) 문제 해결 아이디어 1이상 1000000이하인 길이 n인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 구하는 문제다. 첫번째 오류. 메모리 초과 dp테이블의 크기를 n만큼 생성했는데 최대값이 1000000인 탓에 메모리 초과가 난 것 같다. 그래서 리스트를 사용하지 않고 값 2개를 저장할 수 있는 변수 2개(a, b)를 생성하여 문제를 해결했다. 두번째 오류. 시간초과 1%까지 되다가 시간초과가 났다. 15746으로 나눈 나머지를 출력시켜야 하는데 그냥 그 값을 출력시키도록해서 생긴 문제였다. 세번째..
[백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다. 2747번은 n의 범위가 45이하 자연수이고 2748번은 n의 범위가 90이하 자연수이다. 일단 두 문제 모두 일반 재귀로 피보나치 수를 구하려면 시간복잡도가 (2**n)으로 45이면 2**45(약 10**12), 90이면 2**90(약 10**27)으로 시간 초과가 나올 것이다. 그러므로 dp로 풀어야한다! (풀이1) 반복문 이용 풀이 시간: 5분 이내 1) 문제 해결 아이디어 2) 소스코드 n = int(input()) # 1. 45이하 자연수, 2. 90이하 자연수 d = [0] * (n + 1..
