문제 링크https://www.acmicpc.net/problem/1303 TIL각각의 팀을 구별해서 힘을 계산하기 위해 dict 를 사용함dfs보다는 bfs가 속도가 더 빨라서 bfs 채택처음 순회를 하러 들어가게 되면, team이라는 변수를 통해 'B'인지, 'W'인지 파악하도록 함 Codefrom collections import dequeN, M = map(int, input().split())grid = [ list(input()) for _ in range(M) ]visited = [ [False]*N for _ in range(M) ]dir = [(0,1), (1,0), (0,-1), (-1,0)]powers = {'B':0, 'W':0}q = deque()for i in range..
문제 링크https://www.acmicpc.net/problem/2302 TILdp[0] 에 대해 초기화가 필요하지 않다고 생각해 거의 안했는데, 이 부분이 큰 문제가 될 수 있음항상 생각해보기인덱스를 조절하여 문제를 푸는 경우 -> fix[i] + fix[i-1] + fix[i+1] 이런 경우에는 i-1, i+1이 IndexError 발생할 수 있으니 꼭 확인해보기 !! Code[ 리스트 두 개 사용]N = int(input())M = int(input())fixed = []for _ in range(M): fixed.append(int(input()))dp = [0]*41 # 좌석의 개수에 따른 경우의 수. ex)dp[3]은 3개의 좌석에 앉을 수 있는 경우의 수if N==1: ..
문제 링크https://www.acmicpc.net/problem/15988 TIL그냥 주어진 범위 그대로 배열을 초기화해서 사용하면 메모리 초과 뜸N의 범위가 크길래 Top-down으로 구현하려고 함시간초과 발생testcase 의 max값을 구했다면 bottom-up도 가능추가로 1초 제한인데 최대가 1,000,000(100만)이기 때문에 bottom-up으로 해도 O(N)으로 1초 충분히 가능 CodeT = int(input())testcase = []for i in range(T): testcase.append(int(input()))MOD = 1_000_000_009end = max(testcase)dp = [0]*(end+1)dp[1] = 1dp[2] = 2dp[3] = 4for i..
(( 다시 풀어보기 & 외우기 )) 문제 링크https://www.acmicpc.net/problem/10844 TIL처음에 생각한 것: 끝자리 숫자에 따라 추가되는 개수가 다른데 어떻게 처리할까?혹시 규칙이 있을까 싶었고, 3까지했는데 있는 거 같아서 대충 점화식 세웠으나 틀림이런 경우는 확실히 표기가 있으면 편하다고 생각했는데끝자리에 맞춰 2차원 배열 생성하는 방법이 있엇음 !! (아래처럼)dp = [[0]*10 for _ in range(N+1)]for i in range(1,10): dp[1][i] = 1여러 조건으로 분기할거면 꼭 elif 로 분기하기 !!!!!안그러면 if 나와서 또 다른 if 들어가서 원치않는 결과 발생 가능성 증가 !!!!! 모듈러 연산은 MOD = 1_000_000_0..
(( 다시 풀기 & 외우기 )) 문제 링크https://www.acmicpc.net/problem/15486 TILdp는 문제에 따라 미래 dp 배열을 기준으로 계산(업데이트)해야 하는 경우도 있음 주의 !!!!!!!!!!특히 실행 조건(시간, 돈 등)이 걸려있을 때, 미래를 기준으로 업데이트하는 게 편함아래 경우 예시dp[i+1] = max(dp[i], dp[i+1])\# 그리고 미래의 dp에 대해 상담 한 경우 업데이트if i + T[i] N: # index 확인 dp[i+T[i]] = max(dp[i+T[i]], dp[i]+P[i])100만(1,000,000) 이상부터는 sys.stdin.realine 사용하기 !! (혹은 sys.stdin.read)아무튼 그냥 input()으로 받는 거는..
((외우기))문제 링크https://www.acmicpc.net/problem/15989 TIL1+2+1, 2+1+1 이런 건 이미 1+1+2로 포함되므로 중복즉, "오름차순으로만 조합"하면 중복을 피할 수 있음이런 식으로 조합만을 계산할 때, 오름차순 생각하기 !!!!! (특히 조합의 원소가 정해져있을때)dp[0]을 지정하는 것이 낯설지만 기억하기 !! 뭔가 dp[1]은 1인 경우에 대해서 나타내기 때문에 0은 범위에 없어서 지정하는 것이 어색그치만 base로 필요한 경우가 많기에 생각해주기 이런 식으로 조합의 원소가 정해져 있는 경우bottom - up 방식for num in [1, 2, 3]: # 가능한 숫자 오름차순으로 for i in range(num, 10001): # num 이상..
