전체 글

1912번 파이썬

ary를 deepcopy해서 새로운 리스트 p(dp를 이용하기 위한 리스트)를 만들어준다. 그리고 나서 두번째 인덱스부터 마지막 인덱스까지 이전 dp에 현재 ary의 값을 더한 값이 ary의 본연의 값보다 큰지 확인하고 크면 해당 dp 인덱스를 그 값으로 교체해준다! 그리고 최종적으로 연속된 값이 가장 큰 값을 p 리스트에서 출력해준다. import sys,copy input = sys.stdin.readline n = int(input()) ary=list(map(int,input().split())) p=copy.deepcopy(ary) for idx in range(1,n): if p[idx] < (p[idx-1]+ary[idx]): p[idx]=p[idx-1]+ary[idx] print(max(p))

14002번 파이썬

res=[] for num in ary: if num not in res: res.append(num) 처음엔 모든 인덱스를 한번씩 돌아서 중복되지 않게 res에 추가하고 마지막으로 정렬해서 출력했는데 틀렸다고 떴다.. 아래 코드는 1부터 n-1번째 인덱스까지 dp를 이용해서 p[i]에 최대 수열의 길이 값을 넣는 코드이다. 최소 수열 길이는 1이기 때문에 모든 값을 1로 초기화하고 i를 1부터 n-1까지 반복해서 i번째까지의 수열 중에서 최대 길이가 되는 수열의 길이를 구해준다. ex) {10, 20, 10, 30, 20, 50} 에서 i가 2면 20까지의 수열에서 수열의 길이를 구한다. p[j]에 +1을 해준 이유는 j번째 인덱스가 i 번째 값보다 작고 이는 최대 수열의 길이에 j다음 i가 포함되는 ..

1463번 파이썬

import sys input = sys.stdin.readline n = int(input()) p=[0 for _ in range(n+1)] if n>=2: p[2]=1 if n>=3: p[3]=1 for num in range(4,n+1): cnt=0 temp=[p[num-1]+1] if num%2==0: temp.append(p[int(num/2)]+1) if num%3==0: temp.append(p[int(num/3)]+1) p[num]=min(temp) print(p[n])

5430번 파이썬

처음에 r이 실행될때마다 reverse를 해줬는데 시간 초과 에러가 그 부분에서 떠서 left를 이용해서 뒤집기를 했을 때 값을 바꿔주는 방식을 이용했다. 굳이 deque를 안썼어도 left가 true일때 앞에껄 빼주고 false일때는 n을 알고 있기 때문에 뒤에껄 빼주면 된다! ary를 처음에 리스트로 만들때 1부터 -2까지 긁어모은 이유는 0번째는 '['로 되어있고 -1번째는 ']'로 되어있기 때문이다! 그리고 ary를 빈리스트인 '[]'로 입력 받았을 때 ary에 [''] 이런식으로 저장되기 때문에 if문으로 처음에 처리해줬다. 다른 부분이 다 맞았는데 틀렸다고 떠서 설마 출력 type가 문제인가 싶어서 다른 사람이 한 것을 봤더니 map으로 deque에 있는 숫자들을 int로 바꿔서 출력해야하는 ..

2193번 파이썬

15990번 문제와 비슷한 방식을 이용해서 p[idx][0]은 idx-1번째 중 뒤에가 0으로 올때와 1으로 올때의 경우를 더해주었고 p[idx][1]은 idx-1번째 중 뒤에가 0으로 끝날때의 수를 더해주었다. import sys input = sys.stdin.readline n = int(input()) p = [[0 for _ in range(2)] for _ in range(91)] p[1] = [0,1] p[2] = [1,0] p[3] = [1,1] for idx in range(4,n+1): p[idx][1]=p[idx-1][0] p[idx][0]=p[idx-1][0]+p[idx-1][1] print(sum(p[n]))

15990번 파이썬

처음엔 아래 코드처럼 p[n]을 구하기 위해서 p[n-1]에 앞뒤로 1을 붙여주거나 p[n-2]에 2를 붙여주거나 p[n-3]에 3을 붙여주는 방법으로 해봤는데 시간 초과 에러가 떴다. import sys input = sys.stdin.readline t = int(input()) p = [(0) for _ in range(100002)] div = 1000000009 p[1] = [['1']] p[2] = [['2']] p[3] = [['1', '2'], ['2', '1'], ['3']] for _ in range(t): n = int(input()) if n > 3: for num in range(4, n+1): if p[num] != 0: continue ary = [] for i in range..

11052번 파이썬

이 문제는 p[n]과 i가 1부터 n의 절반까지인 p[n-i] + p[i] 중 값이 최대인걸 p[n]에 저장하는 방식을 이용했다. 즉 p[4]의 경우 p[3]+p[1] or p[2] + p[2] or p[4] 중 최대인 값이 p에 저장되는 dp 방법을 이용했다. import sys input = sys.stdin.readline n = int(input()) ary = list(map(int,input().split())) p=[0]*(n+1) p[1]=ary[0] for num in range(2,n+1): temp=[ary[num-1]] for idx in range(1,int(n/2)+1): temp.append(p[num-idx]+p[idx]) p[num]=max(temp) print(p[n])

14503번 파이썬

먼저 청소한 구역은 벽이랑 구분하기 위해서 2로 색칠한다. 그 다음 2번처럼 작동하기 위해선 네 방향 모두 왼쪽으로 회전해서 0인 구역이 있을 경우 그 위치로 이동해서 청소를 한다. # (d+3)%4를 할 경우 현재 바라보고 있는 방향의 왼쪽 방향으로 바뀐다. 만약 네 방향 모두 청소할 구역이 없을때 방향을 유지한채 후진한다. 후진했을 경우 벽면이 있을때(1일때)는 cnt를 출력하고 종료하고 청소를 한 구역일 때는 다시 2번으로 가서 네 방향 회전을 시작한다. 반복문이 많다보니 pypy로 제출했다. import sys,math input = sys.stdin.readline from collections import deque n,m = map(int,input().split()) r,c,d = map(..

2573번 파이썬

먼저 빙산 주변에 바닷물이 있는지 다른 ary에 따로 저장해줘야한다. 한번에 빼지 않으면 중간에 0이 되는 값도 있어서 빼면 안되는 값도 추가적으로 빼진다. 먼저 for문을 돌려 bfs로 탐색한다. bfs를 탐색하면서 빙하 주변에 바닷물이 있으면 그만큼 m_ary에 저장해준다. 만약 count가 1이면 빙하는 아직 갈라져 있지 않은 상태이고 count가 0이면 즉 모든 빙하들 값이 0이면 두 덩어리 이상으로 분리되지 않는 경우이기 때문에 0을 출력해준다. count가 2이상일 경우엔 덩어리가 두개 이상으로 분리돼서 bfs문이 두번이상 돌게 된다는 뜻이다. 처음엔 빙산의 idx만 list로 따로 모아서 주변에 있는 바닷물 만큼 한번에 빼주고 0이 된 빙산은 빙산list에서 빼고 bfs문을 돌려 방문한 노드..

2468번 파이썬

처음에 visited를 append로 추가하는 식으로 방문한 것을 관리했더니 시간소요가 컸다. 다른 사람들을 보니까 visited를 0값을 1로 바꿔주는 방법을 쓰길래 나도 사용해봤더니 시간 초과 에러는 뜨지 않았다!! 이 문제는 간단하게 bfs를 이용해서 풀 수 있다. 높이의 최솟값부터 최댓값까지 잠기는 높이를 for문으로 돌려주면 되고 모든 idx를 검사해서 h보다 크고 방문하지 않는 지점이 있다면 bfs문을 돌려서 그 지점의 최대 영역을 방문 지점에 넣고 cnt를 1증가 시켜준다. 새로운 높이마다 최대 영역이 되는 구간이 달라지기 때문에 visited를 항상 초기화해주어야 하고 (# visited=[[0]*n]*n 이렇게 작성할 경우 [0]*n이 n번 복사되는 것이므로 한 행의 값이 바뀌면 모든 행..