Python

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번 복사되는 것이므로 한 행의 값이 바뀌면 모든 행..

2579번 파이썬

n번째 계단을 밟았을 때 최댓값을 구하는 경우는 1. n-1번째 계단을 밟았을 경우 n-2번째 계단을 밟으면 안되기 때문에 n-3번째 계단까지의 최댓값에 n-1번째 계단값과 n번째 계단값을 더해준다. 2. n-2번째 계단을 밟았을 경우 n-2번째 계단까지의 최댓값에 n번째 계단값을 더해준다. 그리고 n이 1일 경우랑 2일 경우를 구분해주지 않으면 index error가 날 수 있다! import sys input = sys.stdin.readline n = int(input()) ary = [int(input()) for i in range(n)] count = [0]*301 if n == 1: count[1]=ary[0] elif n == 2: count[2]=ary[0]+ary[1] else: cou..

2108번 파이썬

collections에 있는 counter를 이용함 산술평균의 경우 처음엔 f-string을 썼는데 계속 틀렸다고 해서 round로 바꿨더니 해결됐다..! f-string이 특정 값일때 반올림을 잘 못하는 것 같은데 아마 첫째자리가 5인 음수이지 않을까라는 생각이 든다. counter의 most_common이라는 내장함수는 (숫자, 횟수)를 데이터 갯수가 많은 순으로 리스트로 리턴해준다. 미리 ary를 sort해놨기 때문에 첫번째랑 두번째 횟수가 동일한지만 비교하면 된다.(횟수가 동일하면 앞에꺼가 뒤에보다 더 작은 값임) import sys from collections import Counter input = sys.stdin.readline N = int(input()) a = [int(input()..

5014번 파이썬

처음에 조금 많이 틀려서 문제가 없는데 뭐가 문제인지 찾아봤다. 아무래도 처음 층을 방문 처리를 안해줘서 처음 층으로 돌아왔을 때 문제가 되는 것 같다. for 문도 문제가 되는 것 같아서 if로 바꿔서 했더니 잘됐다. import sys from collections import deque input = sys.stdin.readline f,s,g,u,d = map(int, input().split()) def bfs(s,f): queue = deque([s]) count = [0]*(f+1) count[s]=1 while queue: floor = queue.popleft() if floor == g: print(count[g]-1) return if (floor+u)0 and not count[fl..

1697번 파이썬

bfs를 이용한 문제 import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) queue = deque([n]) count = [0]*100001 while queue: roc = queue.popleft() if roc == k: print(count[k]) break if 0