전체 글60 [BOJ] Python 백준 상자넣기(1965) https://www.acmicpc.net/problem/1965 부분 수열 dp 문제와 매우 유사한 문제이다. 제일 긴 부분 수열 문제처럼 dp 테이블에 1씩 더해주면서 값을 늘려주고 최댓값을 찾으면 된다. 하지만, 마지막 본인 수까지 포함해야함으로 마지막에 max값에 +1을 해준다.import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))dp = [0] * Nfor i in range(N): for j in range(i): if s[j] 회고.부분 수열문제를 최근에 풀어 바로 풀 수 있었던것 같다. 만약 2개월 지난 후 본다면 풀 수 있을까 의문이다... 2024. 11. 26. [BOJ] Python 백준 가장 큰 증가하는 부분 수열(11055) https://www.acmicpc.net/problem/11055 DP의 대표적인 문제라고 할 수 있다. 여기서 주의할 점은 갯수가 아닌 값을 더해서 최댓값을 찾는 것이다.우선 dp 테이블을 s와 동일하도록 구성해주고, j 부터 i까지 가는 도중에 s[j] import sysinput = sys.stdin.readlineN = int(input())s = list(map(int,input().split()))dp = s[:]for i in range(N): for j in range(i): if s[i] > s[j]: dp[i] = max(dp[i], dp[j]+s[i])print(max(dp)) 회고.처음에 가장 큰 증가하는 부분 수열을 dp테이블 초기화 과정에서.. 2024. 11. 24. [BOJ] Python 백준 돌게임(9655) https://www.acmicpc.net/problem/9655 해당 문제는 2개의 풀이가 가능하다. 그리디 풀이 방식import sysinput = sys.stdin.readlineN = int(input())# 1개 혹은 3개chk = -1while N >0: chk = -chk if N - 3 >0: N -= 3 else: N -= 1if chk == 1: print("SK")else: print("CY") dp 풀이 방식import sysinput = sys.stdin.readlineN = int(input())dp = [False] * (N+1)dp[1] = Trueif N >= 2: dp[2] = Falseif N >= 3: .. 2024. 11. 22. [BOJ] Python 백준 주사위 쌓기(2116) https://www.acmicpc.net/problem/2116 제한된 조건 내에 최대 값을 찾는 완전 탐색 문제이다.백트래킹으로 탐색을 진행했는데 이 코드에서 유심히 봐야할 코드는 조건문이다.조건에서 0와 5은 서로 반대편이므로 total 값에 사용될 수 없다.마찬가지로 [1, 3 ] [2,4]는 만약 위,아래 값을 마추는 주사위로 사용되었으면, 사용이 불가능한 인덱스가 되어버린다.즉, 이전 재귀함수에서 보내준 주사위 윗값이 같은 인덱스를 찾고 그 인덱스와 연관된 ([1, 3 ] [2,4], [0,5]) 값일 경우를 제외한 모든 값중 가장 큰값을 더한 후 다음 재귀로 넘겨주면 된다.import syssys.setrecursionlimit(10**5)input = sys.stdin.readlineN =.. 2024. 11. 22. 이전 1 2 3 4 5 ··· 15 다음