신을 모시는 사당
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 292 | 130 | 101 | 48.325% |
문제
신을 모시는 사당에는 신을 조각한 돌상 N개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서있다. 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다.
궁극의 깨달음을 얻기 위해서는 가능한 한 많은 금색 돌상들이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 아래와 같이 정의된다.
| (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) |
창영이는 궁극의 깨달음을 얻을 수 있을까?
입력
첫째 줄에 돌상의 개수 N이 주어진다.
둘째 줄에 돌상이 나열된 순서대로, 각 돌상이 바라보고 있는 방향이 주어진다. 입력의 편의상 왼쪽은 1, 오른쪽은 2라고 하자.
출력
최대한 많은 깨달음을 얻기 위해 금을 칠하였을 때, 얻을 수 있는 깨달음의 양을 출력한다.
제한
- 1 ≤ N ≤ 100,000
예제 입력 1
5
1 1 2 1 2예제 출력 1
2예제 입력 2
1
1예제 출력 2
1예제 입력 3
2
1 2예제 출력 3
1힌트
칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라.
n = int(input())
statues = list(map(int, input().split()))
# result = 1
# def goldpaint(s_list):
# return abs(s_list.count(1) - s_list.count(2))
# if n == 1:
# print(result)
# else :
# # 0 ~ n - 1
# for i in range(n - 1):
# print(i)
# if result >= n - i :
# break
# for j in range(i + 1):
# tmp = goldpaint((statues[j : n - i + j]))
# if result < tmp :
# result = tmp
# print(result)
left_max = 0
right_max = 0
total_max = 0
for i in range(len(statues)):
if statues[i] == 1:
left_max += 1
right_max -= 1
if right_max < 0 :
right_max = 0
tmp_max = max(left_max, right_max)
else :
left_max -= 1
right_max += 1
if left_max < 0 :
left_max = 0
tmp_max = max(left_max, right_max)
if tmp_max > total_max :
total_max = tmp_max
print(total_max)
배울점
오늘 처음으로 DP 관련 문제를 풀었다. 처음에 Greedy 방법으로 테스트 케이스는 잘 풀렸지만, 막상 제출하니 시간 초과라는 결과가 나왔다. 위의 문제는 연속합 문제와 상당히 유사한데 구현은 간단하지만 안에 있는 로직은 간단하지 않다.
1 1 2 2 1 1를 예를 들어보자.
여기서 핵심은 각 요소를 차례로 돌면서 요소가 무조건 포함된 리스트에서 좌 방향의 최대 길이와 우 방향의 최대 길이를 구하고 그 중 최대 길이를 현재 저장된 최종 최대 길이와 비교하여 값을 변경 해주는 것이다.
처음 1 만 있을 때는 좌 방향 최대 길이는 1 우 방향 최대 길이는 0 이다. 최종 최대 길이는 1이다.
다음 1이 추가되어 1 1가 되면 좌 방향 최대 길이는 2 우 방향 최대 길이는 0이다. 최종 최대 길이는 2로 바꿔준다.
다음 2가 추가되어 1 1 2가 되면 2가 무조건 포함되어야 하기 때문에 좌 방향 최대 길이는 1 우 방향 최대 길이는 1이다. 최종 길이가 1이기 때문에 최종 최대 길이는 2로 유지
다음 2가 추가되어 1 1 2 2가 되면 새롭게 추가된 2가 포함되어야 되기 때문에 좌 방향 최대 길이는 0 우 방향 최대 길이는 2이다.
1 1 2 2 1은 좌 방향 최대 길이는 1 우 방향 최대 길이는 1이다.
`1 1 2 2 1 1은 좌 방향 최대 길이는 2 우 방향 최대 길이는 0이다.
따라서 최종 최대 길이는 2이다.
이걸 구현하게 되면 새롭게 추가되는 요소에 맞는 방향 최대 길이는 + 1 를 해주고 맞지 않은 방향 최대 길이는 - 1 를 해준다. 단, 음수가 될 경우 0으로 전환해준다. 왜냐하면 최종 최대 길이는 음수가 될 수 가 없다. 그리고 두 방향 길이를 비교하여 더 큰 길이를 저장해놓은 최종 최대 길이와 비교해주어 더 큰 값으로 교체해준다.
앞에 1 1 2 2 1 1 를 예로 들자면 ,
| List | Left_max | Right_max | Total_max |
|---|---|---|---|
1 | 1 | -1 => 0 | 1 |
1 1 | 2 | -1 => 0 | 2 |
1 1 2 | 1 | 1 | 2(1보다 커서 유지) |
1 1 2 2 | 0 | 2 | 2 |
1 1 2 2 1 | 1 | 1 | 2(1보다 커서 유지) |
1 1 2 2 1 1 | 2 | 0 | 2 |
연속합
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 128 MB | 115927 | 41726 | 29420 | 34.695% |
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 1
10
10 -4 3 1 5 6 -35 12 21 -1예제 출력 1
33예제 입력 2
10
2 1 -4 3 4 -4 6 5 -5 1예제 출력 2
14예제 입력 3
5
-1 -2 -3 -4 -5예제 출력 3
-1n = int(input())
numbers = list(map(int, input().split()))
tmp_max = numbers[0]
total_max = numbers[0]
for i in range(1, n):
tmp_max = max(numbers[i], numbers[i] + tmp_max )
if tmp_max > total_max :
total_max = tmp_max
print(total_max)배울점
DP 기본적인 문제이지만 DP를 잘 모르는 나 같은 사람이 풀면 한참을 고민해야 시간 초과가 나지 않고 풀 수 있다. 핵심은 지속적으로 값을 더하고 더한 값을 새로운 요소와 비교하여 새로운 요소가 클 경우, 더한 값을 새로운 요소로 바꿔준다. 이 과정에서 큰 값은 최종 최대 값으로 저장해준다.
예를 들어,
2 1 -4 3 4 -4 6 5 -5 1일 경우
| List | now_max | new | total_max |
|---|---|---|---|
2 1 | 3 ( 2 + 1) | 1 | 3 |
2 1 -4 | -1 (3 + -4) | -4 | 3 |
2 1 -4 3 | 2 (-1 + 3) vs 3 => 3 | 3 | 3 |
2 1 -4 3 4 | 7 (3 + 4) | 4 | 7 |
2 1 -4 3 4 -4 | 3 (7 + -4) | -4 | 7 |
2 1 -4 3 4 -4 6 | 9 (3 + 6) | 6 | 9 |
2 1 -4 3 4 -4 6 5 | 14 (9 + 5) | 5 | 14 |
2 1 -4 3 4 -4 6 5 -5 | 9 (14 + -5) | -5 | 14 |
2 1 -4 3 4 -4 6 5 -5 1 | 10 (9 + 1) | 1 | 14 |
따라서 정답은 14가 된다. now_max는 더한 값과 새로운 요소 중 더 큰 값으로 저장한다.
