728x90 반응형 알고리즘109 [백준] 11726번: 2×n 타일링 - python ×https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 기본 DP문제. 항상 DP를 풀면서 생각한건 고등학교때 수2?에 나오는 점화식 문제를 생각이 난다. 저장소 만든 다음에 설마 이건가 하고 점화식을 만들어서 대입하면 풀린다. 고딩때도 비슷햇다 n = int(input()) dp = [0] * 1001 dp[1] = 1 dp[2] = 2 dp[3] = 3 for i in range(4, 1001): dp[i] = dp[i-1] + dp[i-2] print(dp[n] %.. 2024. 3. 28. [백준] 1149번: RGB거리 - python https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 쉽지 않았던 dp문제. 값을 업데이트 해나가는 방식이 접근하기 어려웠다. 최소값은 전에 있는 것만 비교하면 되기 때문에 i-1과 비교하여 그 자리를 업데이트한다. 그러면 각 R G B에 대한 최소값이 업데이트 되는데 마지막에 그 3가지 중 최소값을 찾으면 되는 문제이다. n = int(input()) arr = [] for i in range(n): R, G, B = map(.. 2024. 3. 28. [백준] 2468번: 안전 영역 - python https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 무지성으로 가장 큰 값을 기준으로 for문을 돌리면서 한번씩 한번씩 BFS를 진행한다. 그리고 할때마다 값을 answer리스트에 추가해주고 최종으로 answer에서 가장 큰 값을 뽑아낸다. 처음 작성한 코드. 그러나 69퍼에서 바로 런타임에러 발생.. 생각보다 BFS에서 상당히 자주 일어나는 것 같다. 이럴때 런타임에러가 발생하는 이유는 모든 영역이 1일때 for문이 제대로 작동을 안하기 때문이었다. f.. 2024. 3. 28. [백준] 5014번: 스타트링크- python https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 숨바꼭질과 비슷한 패턴의 BFS문제. 사실 난 DFS를 좋아하는데 거의 안쓰는 것 같다. 쨋든 숨바꼭질과 거의 유사하게 작성했는데 계속 83퍼쯤에서 에러가 계속 터졌었다. 왜 그런지하고 계속 생각하다가 틀린 이유를 모르겠어서 질문게시판을 뒤지다가 정답을 알았는데 이 테스트코드 넣은사람은 정말 꼼꼼한거같았다. 엘리베이터 층을 0층부터 생각하고 짜서 에러가 발생한 것이었다.. ㅋ from collections i.. 2024. 3. 28. 이전 1 ··· 18 19 20 21 22 23 24 ··· 28 다음 728x90 반응형
