[백준] 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으로 나눈 나머지를 출력시켜야 하는데 그냥 그 값을 출력시키도록해서 생긴 문제였다. 세번째..
[백준] 2749번 - 피보나치 수 3 (한줄평) 메모리 초과를 해결하지 못해 다른 사람의 풀이를 참고한 문제! 아예 생각조차 하지 못한 방식으로 해결이 가능하다... 답을 안봤으면 절대 못풀었을 문제^^; 유사 문제: 2747, 2748 https://hseungyeon.tistory.com/294 [다이나믹 프로그래밍] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 [백준] 2747번 - 피보나치 수, 2748번 - 피보나치 수 2 (한줄평) 다이나믹 프로그래밍으로 해결할 수 있었던 문제! 2가지 문제는 n번째 피보나치수를 구하는 문제로 두 문제의 차이는 n의 범위다 hseungyeon.tistory.com 이 문제는 n이 1,000,000,000,000,000,000이하의 자연수 일 때..
[백준] 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..
t = int(input()) # 테스트 케이스 수 for _ in range(t): n = int(input()) # 정수 d = [0] * 11 # 11보다 작은 양수 d[1], d[2], d[3] = 1, 2, 4 for i in range(4, n + 1): d[i] = d[i - 3] + d[i - 2] + d[i - 1] print(d[n]) [백준] 9095번 - 1, 2, 3 더하기 (한줄평) 아이디어만 떠올린다면 쉽게 풀 수 있는 문제! 풀이 시간: 20분 이내 1) 문제 해결 아이디어 11보다 작은 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다. DP문제는 보통 아이디어만 잘 떠올리고 점화식을 세운다면 코드 자체는 간결하게 해결할 수 있는 문제..
