Total

[2011] 암호코드

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 분석 10 ≤ 현재 숫자와 바로 그 앞자리 숫자 ≤ 26일 때, 두자리가 가능한 숫자 dp[i] += dp[i-2] : 앞자리 숫자 앞의 DP[현재숫자인덱스-2]에 저장되어있는 값을 DP[현재숫자]에 넣어줌 1 ≤ 현재 숫자 ≤ 9 dp[i] += dp[i-1] : 앞자리 숫자의 DP[앞자리숫자] 또한 DP[현재숫자]에 넣어줌 풀이 code = list(map(int, input())) n = len(code) dp=[0]*(n+1) dp[0]=1 dp[1]=1 if code[0..

알파코드(DFS)

분석 풀이 """ 알파벳 A에는 1로, B에는 2로 이렇게 해서 Z에는 26을 할당 "BEAN"을 암호화하면 25114 알파벳으로 바꾸면 BEAAD, YAAD, YAN, YKD, BEKD, BEAN ... 암호화된 코드가 주어지면 그것을 알파벳으로 복원하는데 얼마나 많은 방법인 있는지 입력된 코드를 알파벳으로 복원하는데 몇 가지의 방법이 있는지 각 경우를 출력, 그 가지 수도 출력 단어의 출력은 사전순으로 출력 """ code=list(map(int, input())) n=len(code) # 종착점 code.insert(n,-1) # 마지막값

동전 분배하기 (DFS)

분석 풀이 """ N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다. 세 명이 받은 각각의 총액을 계산해 총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력 단 세 사람의 총액은 서로 달라야 합니다. 첫째 줄에는 동전의 개수 N(3

동전 바꿔주기 (DFS)

분석 풀이 """ k가지 동전이 각각 n1, n2, ... , nk개 T원의 지폐를 동전으로 바꿔 주려고한다 입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의금액 pi와 개수 ni가 주어질 때 (i=1,2,...,k) 지폐를 동전으로 교환하는 방법의 가지 수 첫째 줄에는 지폐의 금액 T(0

[2624] 동전 바꿔주기 (DP)

2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 분석 dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수 dp[money] += dp[money - coin * cnt] (money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액, cnt는 사용하는 동전의 개수) 풀이 """ 입력으로 지폐의 금액 T 동전의 가지 수 k 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수 """ t=int(i..

[17610] 양팔저울(DFS, 브루트포스)

17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 분석 풀이 """ 무게가 서로 다른 K개의 추, 모든 추 무게의 합 S {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을 수 없다. K(3

휴가(삼성 SW역량평가 기출문제 : DFS활용)

DP [14501번] 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net bottom up n = int(input()) s = [list(map(int, input().split())) for i in range(n)] dp = [0 for _ in range(n+1)] for i in range(n): for j in range(i karla.tistory.com 풀이 """ N+1일째 되는 날 휴가, 남은 N일 동안 최대한 많은 상담 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P 휴가를 가기 위해 얻을 수 있는 최대 수익 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다. 둘째 줄부터 1일부터 N일까지 순서대로 주..

최대점수 구하기(DFS)

""" N개의 문제, 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. 첫 번째 줄에 문제의 개수N(1

[1167] 트리의 지름(BFS, 그래프)

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 분석 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나 그래프를 인접 리스트로 저장 BFS를 수행하고 탐색할 때 각 노드의 거리를 리스트에 저장 2에서 저장한 리스트에서 임의의 노드와 가장 먼 노드를 찾고, 그 노드부터 BFS 다시 수행 3에서 저장한 거리 리스트 값 중 가장 큰 값을 이 트리의 지름으로 출력 풀이 """ 트리를 구성하는 노드 중 두 노드 사이의 거리가 가장 긴 것 정점개수V V개의 줄에..

[2178] 미로 탐색(BFS)

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 """ 두 정수 N, M(2 ≤ N, M ≤ 100) M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. """ import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] visited= [[False for j in range(m)] for i in r..