목록전체 글 (139)

jae_coding

(백준 알고리즘 문제풀이) 2293번 동전 1

문제 문제 링크 문제 접근 N가지 종류의 동전 -> 가치의 합 K원이 되도록해야한다. 각각의 동전은 몇개라도 사용할 수 있다. 출력: 경우의 수 동전의 종류를 몇가지 사용하는지에 따라 분류한다. (예를들어 3가지면 1가지만 사용했을 경우, 2가지만 사용했을 경우, 3가지를 사용했을 경우를 더한 값이 모든 경우의 수가 된다.) 2차원배열을 사용하면 좋겠지만 메모리 문제로 인하여 1차원 배열을 사용하자 점화식: dp[j] += dp[j-coins[j]] 코드 import sys N, K = map(int, sys.stdin.readline().split()) coins = list() for _ in range(N): coins.append(int(sys.stdin.readline())) coins.sort..
알고리즘 문제/백준 2022. 7. 7. 00:50
(백준 알고리즘 문제풀이) 9251번 LCS(최장 공통 부분 수열)

문제 문제 링크 문제 접근 LCS: 최장 공통 부분 수열 ex)ACAYKP, CAPCAK -> ACAK output: LCS의 길이 예제로 문제를 접근해 보았다. x, y 축의 첫 항의 값은 모두 0으로 고정이다. (margin을 주기 위함) x, y 축에 cross하여 같은 것이 있으면 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값에 + 1해주는 식의 알고리즘이다. 그렇지 않으면, 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값 중 높은 값을 입력하면 된다. 잘 이해가 되지 않으니 그림으로 설명하겠다. 그림1 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 A 0 1 Y 0 1 K 0 1 P 0 1 그림2 0 C A ..
알고리즘 문제/백준 2022. 7. 6. 17:39
(백준 알고리즘 문제풀이) 1465번 스티커

문제 문제 링크 문제 접근 스티커 2n개 구매 -> 2행 N열로 배치 스티커 1장을 떼면 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용불가 (상하좌우 스티커 사용 불가) 모든 스티커가 붙일 수 없는 상황이 되었을때, 각 스티커의 점수 최대의 합을 구하는 프로그램 모든 스티커가 찢어지기 위해서는 좌표 (0, 0)에서는 (1, 1) 또는 (2, 1)으로 가야한다. 그러므로 y 좌표가 0이라면 (x, 0) -> (x+1, 1) or (x+2, 1) 그리고 y 좌표가 1이라면 (x, 1) -> (x+1, 0) or (x+2, 0)으로 이동해야한다. 코드 import sys T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readli..
알고리즘 문제/백준 2022. 7. 6. 16:51
Prev 1 ··· 40 41 42 43 44 45 46 47 Next