본문 바로가기

[BOJ] - Python

 (45)
[백준] 18428 : 감시 피하기 python n을 입력받는다. 그래프 정보를 입력받는다. 탐색할 때 활용하기 위해 선생님의 (행, 열)값을 teachers라는 리스트에 저장한다. 선생님의 위치에서 상하좌우 방향으로 감시하는 함수 watch(x,y)를 구현한다. for문으로 그래프 범위를 벗어나지 않는 선에서 탐색을 하다가 학생을 발견하면 True를 반환한다. 감시 성공여부를 뜻하는 전역변수 answer를 False로 초기화한다. 이후에 감시를 피하는 데에 성공하면 True로 업데이트한다. DFS함수를 구현한다. 시간제한이 넉넉하니 최대 6x6인 그래프에 장애물을 하나씩 세우고 장애물의 개수가 3이 되면 teachers에 저장된 선생님들의 위치에서 상하좌우감시함수를 수행한다. 선생님이 감시를 실패할 때마다 teacher_cnt를 증가시킨다. teac..
[백준] 1912 : 연속합 python https://data-marketing-bk.tistory.com/52 백준 - 1912번 - 연속합[파이썬] 1. 문제 출처 백준 - 1912번: 연속합 문제로 이동하기 우선 링크로 가서 문제를 보도록 하자. 2. 문제 설명 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 data-marketing-bk.tistory.com 위 포스트를 참고했는데 이전까지의 합이 그냥 i번째 숫자보다 작은 경우 이전의 기록들은 무의미하다는 문장이 큰 도움이 됐다. 현재값보다 연속된 수들의 누적합이 더 크다면 그 값을 쓰고, 현재값이 더 크다면 이전 값은 의미가 없으니 현재값으로 갱신을 한다. 현재값과 그 이전값들의 합을 비교하는 것이니 메모리를 추가로 사용할 필요도 없다. n..
[백준] 2156 : 포도주 시식 python 세 잔을 연속해서 마실 수 없기 때문에 (마시는 걸 O, 마시지 않는 걸 X라고 했을 때) OXO : dp[i-3]+dp[i-2]+arr[i] XOO : arr[i-1]+arr[i] 이 두 가지 경우를 생각했는데 마지막잔을 마시지 않아도 된다는 점을 간과해서 문제가 풀리지 않았다. OOX : dp[i-1] 인 경우도 구해서 세 가지 경우 중 최댓값인 걸 dp[i]에 저장하도록 해서 해결했다. import sys input = sys.stdin.readline n=int(input()) arr = [int(input()) for _ in range(n)] dp = [0]*n dp[0] = arr[0] if n>1: dp[1] = arr[0]+arr[1] if n>2: dp[2] = max(dp[1], ar..
[백준] 14002 : 가장 긴 증가하는 부분 수열 4 python n = int(input()) A = list(map(int,input().split())) # A에 저장된 각 값들까지의 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열 # A에 저장된 0번째 수까지의 가장 긴 증가부분수열의 길이는 1이므로 # 1로 초기화함 dp=[1]*n # A에 저장된 1번째값부터 자신의 앞에 있는 수들과 비교를 함 for i in range(1,n): for j in range(i): # 자신이 더 크다면 기존의 증가부분수열의 길이와 # 부분수열에 자기자신을 추가했을 때의 길이 중 더 긴 것으로 업데이트함 if A[i]>A[j]: dp[i] = max(dp[j]+1, dp[i]) # 가장 긴 증가부분수열의 길이를 저장함 order = max(dp) # 증가부분수열의 실제 값을..
[백준] 1932 : 정수 삼각형 python 첫번째행부터 자신의 위에서 나올 수 있는 최대값에 자신을 더하는 방식으로 문제를 풀어나갔다. 0번째열이라면 dp[i-1][j]+자기자신이 답이니 바로 저장하고 열값이 0보다 크다면 dp[i-1][j-1]과 dp[i-1][j]중 더 큰 값에 자기자신을 더한 걸 dp테이블에 저장하도록 했다. n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*n for _ in range(n)] dp[0][0] = arr[0][0] # 1부터 n-1행까지 for i in range(1,n): # 0 부터 i까지 for j in range(i+1): # 0번째 열이면 if j ==0: dp[i][j]=dp[i-1][j]+arr[..
[백준] 12865 : 평범한 배낭 python [물건의 개수]x[가방에 넣을 수 있는 최대 무게] 크기의 dp행렬을 생성하고 0으로 초기화한다. 물건을 하나씩 보면서, 현재 물건을 넣을 수 없다면 기존의 가치값을 그대로 가져오고 넣을 수 있다면 기존의 가치와 현재 물건을 넣을 수 있는 시점에서의 가치 + 현재 물건의 가치 중 큰 값을 저장한다. n,k = map(int,input().split()) item = [[0]*2 for _ in range(n+1)] for i in range(1,n+1): item[i] = list(map(int,input().split())) dp = [[0]*(k+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,k+1): weight = item[i][..
[백준] 1149 : RGB거리 python 전체 비용이 최소가 되기 위해서 마지막집이 R일 때, G일 때, B일 때 모두를 계산하고 그중 최소인 것을 출력한다. 이때 i번째 집은 i-1번째 집과 다른 색이어야 한다는 조건이 있기 때문에 i번째 집이 R인 경우에는 i-1번째 집이 G거나 B여야 하고 i번째 집이 G인 경우에는 i-1번째 집이 R이거나 B여야 하고 i번째 집이 B인 경우에는 i-1번째 집이 R이거나 G여야 한다. n = int(input()) color = [0]*(n) for i in range(n): color[i] = list(map(int,input().split())) for i in range(1,n): color[i][0] += min(color[i-1][1],color[i-1][2]) color[i][1] += min(..
[백준] 24416 : 알고리즘 수업 - 피보나치 수 1 문제에서 말하는 대로 풀었는데 Python3으로 제출하니 시간초과가 나왔고, PyPy3로는 정답판정이 나왔다. n = int(input()) def recursive_fibo(x): global cnt_recursive if x==1 or x==2: cnt_recursive +=1 return 1 return recursive_fibo(x-1)+recursive_fibo(x-2) def dp_fibo(x): global cnt_dp dp = [1]*(x+1) for i in range(3,x+1): dp[i] = dp[i-1]+dp[i-2] cnt_dp += 1 cnt_recursive = 0 cnt_dp = 0 recursive_fibo(n) dp_fibo(n) print(cnt_recursive, c..

티스토리툴바