문제

나의 답안

def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []

    for idx, value in enumerate(numbers):
        while True:
            if not stack:
                break
            if numbers[stack[-1]] < value:
                pre = stack.pop()
                answer[pre] = value     
            else:
                break
        stack.append(idx)
    return answer

** 접근 방법**

• 스택을 사용하여 이중루프를 제거하는 방식
  • LIFO라 이중루프를 사용할 필요가 없음, 새로운 숫자를 스택의 top과 비교
• 더 큰 수를 찾지 못하는 경우를 대비해 answer을 -1로 초기화한다.
• 현재 숫자(value)보다 작은 숫자들만 스택에 남아있고, 더 큰 숫자가 나올 때까지 기다리게 됨
• 현재 값(value)이 스택의 top 값보다 크면(numbers[stack[-1]]) => 더 큰 수를 찾은 것 따라서, 해당 인덱스를 pop하고 answer에 해당 숫자를 업데이트 해준다.

실패 답안1

def solution(numbers):
    dic={}

    for idx, val in enumerate(numbers):
        dic[idx] = val

    for idx, val in dic.items():
        if idx == len(numbers) - 1:
            dic[idx] = -1
            continue
        for j in range(idx, len(numbers)):
            if val < dic[j]:
                dic[idx]=dic[j]
                break
            elif val > dic[j]:
                dic[idx]=-1

    return list(dic.values())

데이터와 인덱스값을 구분하기 위해 딕셔너리를 사용했다. 인덱스를 키 값으로 저장해서 값을 변경할 때 편리하게 변경하고 싶었다. 그러나 괜히 복잡하게 인덱스 값을 별도로 구별할 필요가 없는 문제라는 것을 알게됐다.

실패 답안2

def solution(numbers):
    answer = []
    tf = True
    for i in range(len(numbers)):
        tf = False
        for j in range(i+1, len(numbers)):
            if numbers[i] < numbers[j]:
                answer.append(numbers[j])
                tf = True
                break
        if tf != True:
            answer.append(-1)
    return answer

그래서 접근한 두번째 방법 단순 리스트로 bool 변수를 두어 더 큰수를 찾았는지를 체크하고, 더 큰수가 없으면 -1을 추가해주는 로직이다. 그러나 여전히 이중루프를 사용하게 되면서 n^2의 시간 복잡도를 가지게 된다.. 결과는 시간초과

문제

나의 답안

def solution(people, limit):
    answer = 0
    people.sort()
    s=0
    e=len(people)-1

    while s<=e:
        if people[s]+people[e]>limit:#합이 더 크면
            e-=1#end를 줄여서 합을 줄여준다
        else:
            s+=1
            e-=1
        answer+=1

        if s==e:
            answer+=1
            break
    return answer

** 접근 방법**

• 그리디 문제이다. 투포인트를 사용하여 s,e를 조절하여 조건에 맞는 값을 찾아준다.
• 배열을 정렬해주고, 합이 더 크면 e를 줄여 합을 줄여준다.
• 반대의 경우에는 s를 증가시키고 e를 줄여 다음 경우의 수를 찾아준다.
• s와 e가 같아지는 경우(배열의 모든 요소를 탐색한 경우) answer를 늘리고 while문을 종료한다.

문제

나의 답안

n,m=map(int,input().split())
s=[]
res=-1

for _ in range(n):
    s.append(list(input()))

for col in range(n):#행 
    for row in range(m):#열
        for i in range(-n,n):#행 방향 공차
            for j in range(-m,m):#열 방향 공차
                num=''#완성된 숫자 저장
                x,y=row,col#열, 행

                while x>=0 and x<m and y>=0 and y<n:#입력된 범위 안에서
                    if i==0 and j==0:#공차가 0이면 같은 칸을 선택한 것(문제 조건 위배)이고
                                    #무한루프 되므로 정지
                        break
                    #가능한 숫자 조합
                    num+=str(s[y][x])
                    if int(int(num)**0.5)**2==int(num):#어떤 성수를 제곱한 수인지(완전제곱수)
                        res=max(int(num),res)#최대 제곱수 구하기

                    y+=i#행 증가
                    x+=j#열 증가

print(res)

** 접근 방법 **

• 1. 행의 공차를 구해야 한다. (행의 시작 위치를 지정해야 함)
• 2. 열의 공차를 구해야 한다. (열의 시작 위치를 지정해야 함)
• 3. 완전제곱수를 구하고, 해당 제곱수가 최대인지 판별해야 한다. 위의 3단계를 거치면 된다.
• 행의 공차를 구하기 위해 행을 기준으로 공차를 구해주고(ex-(1,1),(1,2),(1,3)), 열의 공차도 구해준다.
• x와 y 각각을 열과 행으로 초기화 해준다.
• 행과 열 범위 안에서 while 반복문을 돌리는데 이때 공차가 0이면 같은 칸을 선택한 것이므로 서로 다른 1개 이상의 칸을 선택해야 하는 문제 조건에 위배된다. 따라서 해당 공차가 0이면 반복문을 중단한다.
• 공차가 0이 아니라면 가능한 숫자를 계산해준다.
• 해당 숫자가 제곱 수인지 판별하기 위해 제곱근을 계산해준 후 해당 제곱근을 제곱하여 원래 수와 같은지 확인한다.
  • 만약 같다면 완전 제곱수이므로 기존 제곱수와 비교해 최댓값인지 판별한다.
• 위와 같은 과정을 끝내면 다음 행과 열로 넘어가기 위해 y+=i x+=j 을 해준다.
• 모든 반복문을 돌았다면 결과값인 res를 출력해준다.

문제

나의 답안

from collections import deque
import sys

input=sys.stdin.readline

n=int(input())
arr=list(map(int,input().split()))
que=deque()

for i in enumerate(arr):
    que.append(i)

while len(que)>0:
    idx,num=que.popleft()
    print(idx+1,end=' ')
    if num>0:
        que.rotate(-(num-1))
    elif num<0:#num==0인경우는 xx
        que.rotate(-num)#음수*음수=양수

접근 방법

• 덱의 rotate를 사용하면 쉽게 풀 수 있는 문제이다.
• rotate()는 양수를 인자로 넣었을 때 오른쪽 방향(시계방향)으로 회전, 음수를 인자로 넣었을 때 왼쪽방향(반시계방향)으로 회전한다.
• popleft한 값이 양수라면 왼쪽으로 이동하는데, 이때 왼쪽 값을 한번 pop했으므로 num-1만큼 회전해준다.
• 음수라면 오른쪽으로 이동하면 되므로 그대로 이동해준다.

rotate를 원형으로 생각해 이동해줄 때의 값이 헷갈렸다.

문제

첫번째 제출(런타임 에러)

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
g=[[] for i in range(n+1)] #n+1개의 노드를 갖는 그래프 생성
cnt=0

for _ in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
    g[v].append(u)

visited=[0]*(n+1) #방문한 노드 저장, 방문했으면 1로 변경

def dfs(n):
    visited[n]=1
    for i in g[n]:
        if visited[i]==0:#방문하지 않았다면
            dfs(i)#방문처리

for j in range(1,n+1):
    if visited[j]==0:
        cnt+=1
        dfs(j)
print(cnt)

파이썬의 기본 재귀 깊이는 1000이라고 한다. dfs함수를 재귀적으로 호출하고 있으므로 깊이를 확장해주어야 한다. (참고: https://www.acmicpc.net/board/view/85228)

최종 답안

import sys
sys.setrecursionlimit(10**6)#파이썬 재귀 깊이 확장 1000->10^6
input = sys.stdin.readline

n,m=map(int,input().split())
g=[[] for i in range(n+1)] #n+1개의 노드를 갖는 그래프
cnt=0

for _ in range(m):
    u,v=map(int,input().split())
    g[u].append(v)
    g[v].append(u)

visited=[0]*(n+1) #방문한 노드 저장, 방문했으면 1로 변경

def dfs(n):
    visited[n]=1
    for i in g[n]:
        if visited[i]==0:#방문하지 않았다면
            dfs(i)#방문처리

for j in range(1,n+1):
    if visited[j]==0:
        cnt+=1
        dfs(j)
print(cnt)

접근 방법

• dfs 문제, 지난번에 풀었던 바이러스 문제와 유사한 문제이다.
• 연결 요소는 각 노드들이 연결된 구역이라고 생각하고 접근하면 된다.
• 방문한 노드들은 1로, 방문하지 않은 노드는 0으로 처리해 값이 0이라면 처음 방문한 노드이므로 cnt값을 1증가시켜준다.

문제

나의 답안

import sys
input=sys.stdin.readline

t=int(input())
arr=[]
def prime(n):#소수 판별
    for j in range(2,int(n**0.5)+1):
        if n%j==0: #약수가 존재하므로 소수가 아님
            break   #더이상 검사할 필요가 없으므로 멈춤
    else:
        return True

for _ in range(t):
    n=int(input())
    a=n//2
    b=a
    while True:
        if prime(a)==True and prime(b)==True:
            print(a,b)
            break
        else:
            a-=1
            b+=1

접근 방법

• 문제의 조건에서 두 소수의 차이가 가장 작은 것부터 출력한다고 하였으므로 n의 절반(n//2)부터 쁠마1씩 차를 줄여나가면서 구해주면 된다.
• 에라토스테네스의 체(소수 구하기)를 사용하여 소수를 구할 때의 시간 복잡도를 줄여준다.

문제

나의 답안

from itertools import combinations
import sys
input = sys.stdin.readline

while True:
    s=list(map(int,input().split()))
    k=s.pop(0)
    result=list(combinations(s,6))
    if k==0:
        break
    for i in result:
        for j in i:
            print(j,end=' ')
        print()
    print()

접근 방법

• itertools의 조합 모듈을 이용해주었다.
• 리스트로 숫자들을 입력받고 첫번 째 수(k)를 pop해준다.
• combinations을 사용해 6개의 숫자를 인자로 갖는 조합을 구해주었다.

itertools

• itertools는 파이썬에서 리스트의 조합을 구해주는 유용한 라이브러리이다.

• permutations 하나의 리스트 안에서 조합을 구할 때 사용, 순서를 고려한다.(순열)

  from itertools import permutations

• combinations 하나의 리스트 안에서 조합을 구할 때 사용, 순서를 고려하지 않는다.

  from itertools import combinations

• product 두개 이상의 리스트에서 조합을 구할 때 사용, 똑같은 것을 고를 수 있다.(중복 순열)

  from itertools import product

  
  
  

• 예시

  #test
  from itertools import permutations
  from itertools import combinations
  from itertools import product
  

arr=['가','나','다'] num=[1,2]

print('permutations: ', list(permutations(arr,2))) print('combinations: ', list(combinations(arr,2))) print('product: ', list(product(arr,num))) print('repeat product: ', list(product(arr,repeat=2)))

```python
#result
permutations:  [('가', '나'), ('가', '다'), ('나', '가'), ('나', '다'), ('다', '가'), ('다', '나')]
combinations:  [('가', '나'), ('가', '다'), ('나', '다')]
product:  [('가', 1), ('가', 2), ('나', 1), ('나', 2), ('다', 1), ('다', 2)]
repeat product:  [('가', '가'), ('가', '나'), ('가', '다'), ('나', '가'), ('나', '나'), ('나', '다'), ('다', '가'), ('다', '나'), ('다', '다')]

나의 답안

n=int(input())
s=list(input())

dna = {"AA" : "A", "AG" : "C", "AC" : "A", "AT" : "G", "GA" : "C","GG" : "G",
       "GC" : "T", "GT" : "A", "CA" : "A", "CG" : "T", "CC" : "C", "CT" : "G",
       "TA" : "G", "TG" : "A", "TC" : "G","TT" : "T"}

while True:
    if len(s)==1:
        break
    ss=s[-2]+s[-1]
    if ss in dna:
        del s[-2:]
        s.append(dna.get(ss))
print(*s)

접근 방법

• 표의 내용을 딕셔너리로 선언해주고, 반복문을 통해 문자열의 길이가 1이 될 때까지 반복해준다.
• 조건문을 통해 마지막의 두 문자열(ss)이 딕셔너리 안에 있으면 문자열에서 해당 내용을 삭제하고 딕셔너리의 get을 통해 해당 두 문자열에 해당하는 value값(dna.get(ss))을 가져온다.
• 가져온 문자열을 s에 추가해준다.
• 리스트 요소를 한번에 출력해주기 위해 *s를 사용해주었다.

문제

나의 답안

import sys
import heapq
input=sys.stdin.readline

n=int(input())
arr=[]
for i in range(n):
    x=int(input())
    if x==0:
        if len(arr)==0:
            print(0)
        else:
            mx=heapq.heappop(arr)[1]#튜플(-x,x)에서 x출력하기 위함(본래 최댓값)
            print(mx)
    else:
        heapq.heappush(arr,(-x,x))#우선순위 삽입(힙 정렬)|가장 큰 값을 가장 작게 만듦
        #(가장 작은 값, 실제 값) 최댓값이 루트에 올 수 있도록

접근 방법

• 우선순위 큐 문제이고, heapq를 사용해 구현해주었다.
• heapq을 사용하면 최소힙으로 구성되므로 이를 최대 값이 루트가 되는 최대힙으로 구현해주어야 한다.
• heappush를 사용해 튜플을 arr에 넣어주는데, 이때 최대힙을 구현하기 위해 튜플은 s를 음수로 만들어 (-x,x)로 구성한다.
• 최대힙으로 구현 후 조건에 따라 arr이 빈배열이 아니고 x가 0이라면 최댓값을 출력해주는데, 출력 시에는 원래 최댓값을 출력해주기 위해 힙큐의 두번째 인덱스(heapq.heappop(arr)[1])값을 출력해준다.

문제

나의 첫번째 제출(시간초과)

import sys
input=sys.stdin.readline
t=int(input())

for _ in range(t):
    cnt=0
    n,m=map(int,input().split())
    a_arr=list(map(int,input().split()))
    b_arr=list(map(int,input().split()))
    for i in b_arr:
        for j in range(len(a_arr)):
            if i<a_arr[j]:
                cnt+=1
    print(cnt)

배열로 각 값을 비교하려고 했으나 시간초과가 났다. 잘못된 알고리즘이라 코드를 다시 짜주었다.

나의 답안

import sys
input=sys.stdin.readline
t=int(input())

def find(a,s,e):
    c=-1#cnt에서 +1을해주었기 때문에 -1로 초기화

    while s<=e:
        mid=(s+e)//2#중간 값(이분탐색)

        if a>b_arr[mid]:#a가 b보다 큰 값이라면
            c=mid#인덱스로 초기화
            s=mid+1

        else:#b가 더 크다면
            e=mid-1

    return c

for _ in range(t):
    n,m=map(int,input().split())
    a_arr=list(map(int,input().split()))
    b_arr=list(map(int,input().split()))

    #내림차순 정렬
    a_arr.sort()
    b_arr.sort()

    cnt=0

    for i in a_arr:#a에 대해
        cnt+=find(i,0,len(b_arr)-1)+1#가장 큰 수의 인덱스가 0일 경우에 +1

    print(cnt)

접근 방법

• b에서 a보다 작은 값 중 가장 큰 값을 찾아야 한다. 이를 위해 이분탐색으로 문제를 풀어준다.
• 이분탐색 풀이를 위해 배열 a, b는 내림차순으로 정렬해준다.
• 가장 큰 값의 인덱스 이후는 모두 b가 더 크고, 그 아래는 a가 더 크다는 것이므로 가장 큰 값의 인덱스가 개수가 된다.
• 이분탐색을 위한 함수를 정의해주고, 해당 함수를 호출할 때 a배열과 시작 인덱스 값, 끝 인덱스 값(b배열의 길이-1)을 전달한다.
  • 이 때, 가장 큰 수의 인덱스가 0일 경우를 대비해 +1을 해준다
  • 따라서 함수안에서 인덱스를 저장할 변수(c)는 -1로 초기화해준다.

문제

나의 답안

import sys
import heapq
input=sys.stdin.readline

n=int(input())
result=[]

for _ in range(n):
    heapq.heappush(result,int(input()))#result에 원소 추가
#오름차순 정렬 됨
cnt=0
while True:
    if len(result)==1:
        break
    else:
        d=heapq.heappop(result)+heapq.heappop(result)
        #작은수부터 2개 꺼내서, 2개 더함
        cnt+=d
        heapq.heappush(result,d)#더한 값을 result에 저장-> 모두 구할 때까지 반복
print(cnt)

우선순위 큐를 위해 heapq 모듈의 사용법을 알아야 한다.

접근 방법

• 우선순위 큐, 그리디 문제이다.
• 문제 풀이를 위해 작은 수부터 2개씩 순차적으로 더해주어야 한다. heapq는 오름차순으로 저장되기 때문에 따로 정렬해줄 필요가 없다. (10+20)+(30+40)=100
• 2개 숫자를 더한 값을 cnt에 저장해주고, 2개 숫자의 합을 result에 저장해준다.
• 이를 result에 단일값이 저장될 때까지(len()==1)반복 해주면 된다.

문제

나의 답안

from collections import deque
import sys
input = sys.stdin.readline

m,n=map(int,input().split())

arr=[]
for _ in range(n):
    arr.append(list(map(int,input().split())))#토마토 있는 곳

que=deque()
dx=[1, -1, 0, 0]
dy=[0, 0, -1, 1]
day=0

for i in range(n):
    for j in range(m):
        if arr[i][j]==1:#토마토가 있다면
            que.append((i,j))#해당 위치 큐에 추가

while que:
    x,y=que.popleft()#갈 수 있는 곳의 좌표
    for i in range(4):#상하좌우 탐색
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<m and arr[nx][ny]==0:#익지않은 토마토+좌표 내
            que.append((nx,ny))#덱큐에 추가하고
            arr[nx][ny]=arr[x][y]+1#증가

for k in arr:
    for kk in k:
        if kk==0:
            print(-1)#불가능한 상황
            sys.exit(0)#더 둘러보지 않고 종료
    day=max(day,max(k))#모든 토마토가 익음
print(day-1)

유사문제 2178번 미로 탐색 접근 방법

• 최소일수를 구하기 위해 BFS를 이용한다.

• 토마토 값을 입력받고, 토마토가 있는 곳의 값을 큐에 추가해준다.

• while문을 통해 갈 수 있는 곳의 좌표를 큐에 저장해준다.(모든 값 탐색)

  • 좌표 안에 익지 않은 토마토가 있다면 해당 좌표의 값을 1증가시킨다.(익은 토마토로 변환)

• while문을 통해 모든 좌표를 탐색했다면 이중 반복문을 통해

  • 토마토가 익을 수 없다면 -1을 출력하고 프로그램 종료(exit(0))
  • 아니라면 day를 갱신시킨다.

• 날짜 계산 시 첫날을 포함하므로 -1을 해준 값을 출력한다.

문제

나의 답안

n,f=input(),input()
nn=int(n[:-2]+'00')

while True:
    if nn%int(f)==0:
        break
    nn+=1
nn=str(nn)
print(nn[-2:])

접근 방법

• 문자열 인덱스를 사용해 뒤의 두자리를 잘라주기 위해 문자열로 입력받는다.
• 두자리를 자르고 00을 붙여준 후, while문을 통해 나머지가 0이 나올 때까지 f로 나누어준다.

문제

나의 답안

n=int(input())

dp = [[0] * 10 for _ in range(n + 1)]

for k in range(1,10):
    dp[1][k]=1#0으로 시작하는 수는 계단수가 아니므로 1로 초기화

for i in range(2,n+1):
    for j in range(10):
        if j==0:
            dp[i][j]=dp[i-1][j+1]#0일 때는 +1만 가능
        elif j==9:
            dp[i][j]=dp[i-1][j-1]#9일 때는 -1만 가능
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]#그외에는 +1,-1모두 가능
print(sum(dp[n])%1000000000)

접근 방법

• dp문제이므로 점화식을 도출해내면 된다. n=1일 때 9개, 1,2,3,⋯,9 n=2일 때 17개, 10,21,23,32,34,43,45,⋯,87,89,98
• n=자리 수이고, 1의 자리에 오는 숫자(이하 j)가 무엇인지에 따라 앞에 올 수 있는 숫자가 달라진다. j=0일 때는 +1한 숫자만 올 수 있다. 즉, dp[n][j]=dp[n-1][j-1] j=1~8일 때는 +1,-1모두 올 수 있으므로 dp[n][j]=dp[n-1][j-1]+dp[n-1][j+1] j=9일 때는 -1한 숫자만 올 수 있다. 즉, dp[n][j]=dp[n-1][j+1]

문제

나의 답안

n=int(input())
dp=[1,3]

for i in range(2,n):
    dp.append(dp[i-1]+dp[i-2]*2)
print(dp[n-1]%10007)

접근 방법

• 유사 문제
• DP문제이므로 규칙을 찾으면 된다.
• n=1일 때, 1 n=2일 때, 3 n=3일 때, 5 n=4일 때, 11 이므로 dp[n]=dp[n-1]+dp[n-2]*2라는 점화식을 가짐을 알 수 있다.

문제

나의 답안

cm=[]
for _ in range(9):
    cm.append(int(input()))
hap=sum(cm)
for i in range(9):
    for j in range(i+1,9):
        if hap-(cm[i]+cm[j])==100:
            n1=cm[i]
            n2=cm[j]

cm.remove(n1)
cm.remove(n2)
cm.sort()

for k in cm:
    print(k)

접근 방법

• 9명 중 7명의 난쟁이를 찾아야 하고, 7난쟁이의 키의 합이 100이므로 7명의 키의 합이 100일 때를 찾으면 된다.
• 즉 전체 배열의 합에서 2명의 키를 제외했을 때 100이 되는 순간을 찾으면 된다.

문제

나의 답안

a,b=input().split()

result=[]
for i in range(len(b)-len(a)+1):#길이를 같게
    cnt=0
    for j in range(len(a)):#a길이만큼 자르기
        if a[j]!=b[j+i]:#a를 기준으로 b의 끝까지 검사
            cnt+=1#다르면 1증가, 문자열 전체 count후
    result.append(cnt)#배열에 추가
print(min(result))

** 접근 방법 **

• 브루트포스 문제이므로 A의 길이가 B의 길이보다 작거나 같으므로 A의 길이에 맞춰서 B를 비교해주어야 한다.
• A를 기준으로 A의 길이만큼 B를 잘라서 비교해준다.
• 만약 비교결과가 다르다면 cnt를 1씩 증가해주고, 배열에 cnt값을 추가한다.
• 배열에서 가장 작은 값을 출력해준다. EX 3) A=koder B=(topco)der +4 B=t(opcod)er +5 B=to(pcode)r +4 B=top(coder) +1 가장 최소인 1이 답이 된다.

문제

나의 답안

n=int(input())

dp=[]
dp.append(0)
dp.append(1)

for i in range(2,n+1):
    dp.append(dp[i-2]+dp[i-1])
print(dp[n])

접근 방법

• dp문제, 문제의 조건에 따라 길이가 2이상이면 앞 두자리는 10로 고정된다.
• n=2, 10 n=3, 10+[0,1] =>[100,101] n=4, 10+[00,01,10] => [1000,1001,1010]
• n=4일때, n=3 숫자(뒤에서 2자리) 2개, n=2의 1개의 숫자의 조합
• 따라서 길이 n인 이친수 dp[n]=dp[n-2]+dp[n-1]라는 점화식을 도출해낼 수 있다.

어제 풀었던 피보나치 수2와 유사한 문제이다.

문제

나의 첫번째, 두번째 제출(오답-시간초과)

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

n=int(input())
dp=[fib(i) for i in range(n+1)]
print(dp[n])

동일한 코드를 python3와 pypy3로 제출했다..ㅎ 재귀로 풀면 시간초과가 발생하는 것을 알 수 있었다.

나의 최종 답안(정답)

n=int(input())
dp=[]
dp.append(0)
dp.append(1)

for i in range(2,n+1):
    dp.append(dp[i-1]+dp[i-2])
print(dp[n])

접근 방법

• dp문제, 재귀를 사용하지 않고 풀어주어야 한다.
• n이 0과 1일 땐 각각 0과 1의 값을 가지므로 미리 dp배열에 저장해두고, 반복문을 통해 2부터 n까지 순차적으로 구해준다.

문제

나의 첫번째 답안(런타임 에러)

n=int(input())
arr=[0]
for _ in range(n):
    arr.append(int(input()))

dp=[0,arr[1],arr[1]+arr[2]]
for i in range(3,n+1):
    s=max(dp[i-1],dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i])
    dp.append(s)
print(dp[n])

런타임에러라는 결과가 도출되었다. https://www.acmicpc.net/board/view/81147 를 참고해 수정하였다.

나의 답안(정답)

n=int(input())
arr=[0]
for _ in range(n):
    arr.append(int(input()))

dp=[0,arr[1]]
if n>1:#n이 1이면 arr[1]+arr[2]는 존재x
    dp.append(arr[1]+arr[2])

for i in range(3,n+1):
    s=max(dp[i-1],dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i])
    dp.append(s)
print(dp[n])