본문 바로가기

전체 글

(90)
양팔저울(DFS) 무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이 면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, ⎕은 그릇을 나타낸다.  만약 추의 무게가 {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을 수 없다. K(3 ..
휴가(삼성 SW역량평가 기출문제) 카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다. 현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다. 각각의 상담은 상담을 완료하는데 걸리는 날 수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다. 만약 N = 7이고, 아래와 같이 예약이 잡혔다면 1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다. 하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수 없어 최대 이익이 나는 상담 스케쥴을 짜기로 했다. 휴가를 떠나기 ..
최대점수 구하기(DFS) 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)  ▣ 입력설명 첫 번째 줄에 문제의 개수N(1두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.  ▣ 출력설명 첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.  ▣ 입력예제 5 20 10 5 25 12 15 8 6 3 7 4  ▣ 출력예제 41내가 쓴 코드import syssys.stdin = open("i..
경로 탐색 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성.아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는  1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5  총 6 가지입니다.  그래프에서 경로란 방문한 노느는 중복해서 방문하지 않습니다.  ▣ 입력설명 첫째 줄에는 정점의 수 N(2그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.  ▣ 출력설명 총 가지수를 출력한다.  ▣ 입력예제 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5  ▣ 출력예제 6내가 쓴 코드#내가 쓴 코드def DFS(node): global cnt if node == N: cnt += 1 e..
인접행렬 (가중치 방향그래프) 아래ㅈ그림과 같은 그래프 정보를 인접행렬로 표현해보세요  ▣ 입력설명 첫째 줄에는 정점의 수 N(2그 다음부터 M줄에 걸쳐 연 결정보와 거리비용이 주어진다.  ▣ 출력설명 인접행렬을 출력하세요.  ▣ 입력예제6 9 1 2 7 1 3 4 2 1 2 2 3 52 5 5 3 4 5 4 2 2 4 5 5 6 4 5  ▣ 출력예제 0 7 4 0 0 0 2 0 5 0 5 0 0 0 0 5 0 0 0 2 0 0 5 0 0 0 0 0 0 0 0 0 0 5 0 0내가 쓴 코드#인접행렬import syssys.stdin = open("input.txt",'rt')input = sys.stdin.readlineN,M = map(int, input().split())#2차원배열(행렬 생성)rows = cols = Nmatri..
수들의 조합 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요. 예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있습니다.  ▣ 입력설명 첫줄에 정수의 개수 N(3두 번째 줄에는 N개의 정수가 주어진다. 세 번째 줄에 M이 주어집니다.  ▣ 출력설명 총 가지수를 출력합니다.  ▣ 입력예제5 3 2 4 5 8 126 ▣ 출력예제 2내가 쓴 코드def DFS(v, idx, cur_sum): global cnt if v == K and cur_sum % M == 0: cnt += 1 elif v  모범답안def..
조합 구하기 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.  ▣ 입력설명 첫 번째 줄에 자연수 N(3 ▣ 출력설명 첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.  ▣ 입력예제 4 2  ▣ 출력예제 1 2 1 3 1 4 2 3 2 4 3 4 6 내가 쓴 코드def DFS(v): global cnt if v == (M+1): for i in range(1,M+1): print(result[i], end=' ') print() cnt += 1 else: for j in range(result[v-1]+1..
수열 추측하기 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.  N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. ▣ 입력설명 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.  ▣ 출력설명 첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출..