전체 글 검색 결과
278 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 2208: 보석 줍기 (Python)

접근 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 현재인덱를 포함하는 누적합과, 현재 인덱스가 M번째가 되는 누적합 중 큰 값을 저장하여 문제를 해결할 수 있다. 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [0] prefixSum = [0] for _ in range(N): arr.append(int(input())) prefixS..

2023. 11. 18. 23:19
코딩/백준 (Python)

백준 2228: 구간 나누기 (Python)

접근 https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 점화식을 생각해내기가 어려웠고, 구글을 통해 점화식에 대한 힌트를 얻어 문제를 해결할 수 있었다. n번째 원소까지의 m개 구간합을 구하고자 할 때, max(n-2번째 원소까지의 m-1개 최대 구간합, n-1번째 원소까지의 m개 최대 구간합) + 현재값의 점화식을 통해 문제를 해결할 수 있다. n-2번째 원소까지 m-1개의 구간으로 나누고 n번째 원소를 m번째 구간으로..

2023. 11. 17. 00:36
코딩/백준 (Python)

백준 2169: 로봇 조종하기 (Python)

접근 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 처음엔 dfs를 이용한 dp를 생각해보았지만 해결하지 못했다. 로봇이 왼쪽, 오른쪽, 아래 방향으로만 이동할 수 있다는 점에 착안하여 i 행에서 왼쪽으로 움직일 때와 오른쪽으로 움직일 때를 각각 계산하여 최대값을 구하는 식으로 dp를 이용하여 해결할 수 있었다. 코드 import sys input = sys.stdin.readline N, M = map(int, input().spl..

2023. 11. 5. 16:52
코딩/백준 (Python)

백준 1937: 욕심쟁이 판다 (Python)

접근 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 가장 먼저 단순한 bfs, dfs 문제로 접근했더니 시간 초과로 문제를 해결할 수 없었다. 문제를 해결하기 위해서는 중복 계산을 제거하는 방법을 고안해야 하는데, 중복을 제거하는 방법에는 두 가지 정도로 접근할 수 있었다. 판다는 점점 더 높은 숫자를 향해서만 이동하기 때문에, 대나무의 양이 가장 작은 대나무의 위치부터 계산하여 점점 양이 많은 위치 순서로 탐색한다. 이렇게 탐색할..

2023. 10. 15. 19:03
코딩/백준 (Python)

백준 11048: 이동하기 (Python)

접근 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 얼핏 dfs나 bfs 문제로 보였지만, 다이나믹 프로그래밍을 이용하여 쉽게 풀 수 있었다. (r, c) 칸에서 이동할 수 있는 방향은 세방향으로, (r + 1, c), (r, c + 1), (r + 1, c + 1) 이다. 이 점을 반대로 말하면 (r, c) 칸으로 올 수 있는 바로 전 칸은 (r - 1, c), (r, c - 1), (r - 1, c - 1) 이 세 칸이다. ..

2023. 10. 9. 20:33
코딩/백준 (Python)

백준 10815: 숫자 카드 (Python)

접근 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 그냥 파이썬의 in list 기능을 사용하면 될 것 같지만 이분탐색 알고리즘을 이용하여 문제를 해결하였다. 먼저 주어진 상근이의 숫자 카드들을 오름차순으로 정렬하였다. 간단하게 탐색의 시작 index와 끝 index를 두고, 중간 지점을 기준으로 찾고자 하는 카드가 더 큰지 작은지를 비교해서 이분탐색을 진행하였다. 코드 N = int(input()) sang =..

2023. 4. 15. 01:56
반응형