알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제에 푸는 방법이 있었기에 쉽게 풀 수 있었습니다. 조건을 따라 사용하면 되지만, 이전에 구했던 값을 또 구한다면 시간초과가 생깁니다. 따라서 새로운 값을 구할 때마다 저장해준뒤, 재사용하면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define INF 98765432..

문제 링크입니다. https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리가 주어졌을 때, 쿼리를 기준으로 자신을 포함한 자식노드의 개수를 구하는 문제입니다. 루트노드는 주어졌기 때문에 루트노드부터 시작해 자식의 개수를 찾으면 됩니다. 간선을 저장할 때, 양뱡향으로 저장하기에 부모와 자식 노드의 구분은 이전에 방문을 했는지 여부를 저장하는 check 배열을 통해 했습니다. 자식노드일 경..

문제 링크입니다. https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 자두나무에서 자두가 1초 간격으로 떨어집니다. 2개의 자두나무 중 한 곳에서만 떨어질 때, W이하로 움직이면서 받을 수 있는 자두의 개수를 구하는 문제입니다. (시작점은 1번 자두나무입니다.) 예제 입력의 경우에는 2~3초 동안은 1번 -> 2번 자두나무로 이동 -> 4~5초동안 2번 -> 1번 자두나무로 이동 -> 6~7초동안 1번 이와 같이 움직여 7개를 먹습니다. 이 문제를 풀기 위..

문제 링크입니다. https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net N일이 주어졌을 때, 알약을 먹을 수 있는 방법의 경우를 구하는 문제입니다. 온전한 약을 꺼낸 뒤, 반을 먹고 반은 내려놓는 행위는 W, 반이 남은 알약을 꺼내 먹는 행위를 H라고 합니다. 1일만 약을 먹는다고 했을 때, 나올 수 있는 경우는 WH인 1개뿐이며 2일만 약을 먹는다고 했을 때, 나올 수 있는 경우는 WHWH, WWHH으로 2개가 됩니다. 3일의 경우에는 WHWHWH, WWHHWH,..

문제 링크입니다. https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 격자가 주어지고 중간에 무조건 거쳐야할 점이 주어질 때, 총 경우의 수를 구하는 문제입니다. 수학 중 경우의 수 문제를 풀 때, 한번씩은 풀어봤을 문제입니다. (X, Y)번 격자를 갈 때의 경우의 수는 다음과 같이 구해집니다. 1 1 1 1 1 1 1+1 2+1 ... ... 1 2+1 3+3 ... ... 1 3+1 4+6 ... ... 따..

문제 링크입니다. https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 최소한의 금액으로 N개의 카드를 정확하게 살 때 드는 비용을 구하는 문제입니다. 문제 예시에서 4개를 사려고 할 때 1개 -> 1원 / 2개 -> 5원 / 3개 -> 6원 / 4개 -> 7원이 든다고 할 때, 드는 최소 비용은 1개를 4개 사는 4원일 것입니다. 이를 구하는 과정을 생각해보면 1. 3개 사는 최소 금액 + 1개 금액 2. 2개 사는 최소 금액 + 2개 금액 3. 1개..

문제 링크입니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 규칙에 따라 극장을 앉을 수 있는 경우의 수를 구하는 문제입니다. 규칙은 다음과 같습니다. 1. X번 좌석에 앉을 때 X번만이 아닌, X±1번 좌석에도 앉을 수 있다. 2. 만약 X번 좌석이 VIP 고객일 경우 해당 좌석은 반드시 자신만 앉아야 한다. 다음 규칙을 따라서 VIP 고객의 번호가 주어질 때, 앉을 수 있는 경우의 수를 구해야 합니다. 그렇다면, 간단하게 생각해보겠습니다. 문제와 ..

문제 링크입니다. https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 유명한 모형입니다. 이를 코드로 작성하라는 문제인데, X번째 수를 구하긴 위해서 일단 X번의 행과 열을 알아야합니다. 이를 각각 N, M이라고 했을 때, 값은 다음과 같습니다. arr[N][M] = arr[N-1][M-1] + arr[N-1][M] 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #in..

문제 링크입니다. https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 연속된 수를 곱할 때, 나올 수 있는 최댓값을 구하는 문제입니다. N은 10,000이하의 수이기에 2중 for문을 사용하면 시간초과가 생길 수 있습니다. 따라서 DP를 사용해서 지금까지 곱한 값의 최댓값을 저장해주면서 풀어나가면 됩니다. 문제를 풀기 위해 예시를 생각해보겠습니다. 4번까지 곱한 값의 최댓값을 구하기 위해선 2가지 방법이 있습니다. 1. 3번까지 곱한 ..

문제 링크입니다. https://www.acmicpc.net/problem/9656 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1 or 3개씩 돌을 가져갈 때, 누가 이길 수 있는지 구하는 문제입니다. 돌을 마지막으로 가져가는 사람이 지기 때문에 언제 가져갔는지를 확인할 필요가 없습니다. 따라서 현재 값인 i에서 i-1 or i-3의 값을 확인만 해주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include using namespace std; int N; int dp[1001][2];// 0 -> SK 1 - > CY void solve..

문제 링크입니다. https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 변형된 피보나치 문제입니다. 기존의 피보나치처럼 풀면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include using namespace std; int N, M; long long dx[70]; void solve(){ dx[0] = 1; dx[1] = 1; dx[2] = ..

문제 링크입니다. https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 증가하는 수열 or 감소하는 수열을 둘 다 확인할 때, 가장 긴 길이를 확인하는 문제입니다. 2개의 수열을 확인해야하니 2차원 배열을 이용해서 풀었습니다. 처음 1번은 길이가 둘 다 1이니 1로 저장한 뒤, 다음 값부터 비교해주기 시작합니다. 1. 다음 값이 이전값보다 클 때 -> 증가하는 값을 1을 더한다, 감소하는 값을 1으로 바꾼다. 2. 다음 값이 이전값보다 작을 때 -> 증..