https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 시험이 오늘 끝나서 bob 면접 ppt를 만들고 간단한 문제로 하루를 마무리하였습니다. n개의 주사위 입력이 주어졌을 때, 주사위를 높게 한 줄로 쌓습니다. 이 때 맞닿은 주사위의 면은 같은 수를 가집니다. 이 때 전체 주사위의 긴 한 면의 합이 최대가 되도록 구하면 됩니다. 주사위가 10000개 밖에 없기 때문에 6개의 면 중 옆 면에 해당하는 4개 중 최대값을 고르고 다음 주사위의 6개 숫자 중 맞..
https://www.acmicpc.net/problem/1174 1174번: 줄어드는 숫자 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어 www.acmicpc.net N번째 줄어드는 수를 구하는 문제입니다. 줄어드는 수는 3210 과 같이 내림차순인 수이고 0이 1번째 줄어드는 수 입니다. 문제 접근 방법은 다음과 같습니다. 먼저 1자리 수인 0~9를 리스트에 넣고 0번째 값을 pop 하면서 0 ~ 해당 수의 1의 자리수-1 를 r이라 하면 10 * pop 한 수 + r 을 다시 리스트에 맨 마지막에 넣습니다. 이를 반복하면 9876543210..
https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 주어진 소수의 곱으로 만든 수열 중 N번째 수를 구하는 문제입니다. 간단한 문제이지만 아이디어를 생각하는데 꽤 걸렸습니다. (시험 공부하기 싫어서 푼 문제인데 생각보다 너무 오래걸렸다.....) 우선순위 큐를 오름차순 (top이 가장 작은 값)으로 설정 후 다음의 단계를 거치면 됩니다. 1. 큐의 top값을 주어진 수들과 곱한다. 그리고 pop한다. 2. 큐의 크기가 N..
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소에 바이러스가 포진되어 있을 때 바이러스가 전체에 퍼지는데 걸리는 시간의 최솟값을 구하는 문제입니다. 전체 맵의 최대 크기는 50*50 이지만 문제 조건에 바이러스 최대 개수가 10개라 하였으므로 활성바이러스 10C5가지의 경우가 최대 경우의 수입니다. 풀이는 다음과 같습니다. 1. 전체 바이러스 중 활성바이러스를 고른다. (dfs로 조합을 이용해 미리 구해주었습니다.) 2. 활성바이러스를 bfs로 ..
10840번: 구간 성분 (acmicpc.net) 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N, M의 범위는 1 ≤ N, M ≤ 1,500 이다. www.acmicpc.net 주어진 두 문자열에서 부분 문자열 중 알파벳의 종류와 개수만 같으면 되는 부분 문자열의 최장 길이를 구하는 문제입니다. Ex. abcde / cbaff => 3 단순히 비교하면 두 문자열 길이가 n, m 이라 하면 O(n^2 * m^2) 입니다. (길이 m인 문자열의 부분문자열 1~m까지 길이 같는 건 각각 약 m개 => m^2, n인 것도 마찬가지 => n^2 => 전부 일일이 비교 => n^2 * m^2) 부분..