알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net N원을 2원과 5원으로 거슬러줄때, 최소 동전의 개수를 구하는 문제입니다. 2원과 5원으로 나눠주기에 주지 못하는 값은 -1로 출력하면 됩니다. 배열의 2와 5칸의 값을 1로 만들어준뒤, N원까지 차례대로 동전의 개수를 구하면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include using namespace std; int N; int dx[100001]; void solve(){ dx[5] = 1; dx[2] =..

문제 링크입니다. https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 볼륨이 주어졌을 때, 마지막 곡을 연주할 수 있는지 확인하는 문제입니다. 시작 볼륨이 주어지고, 변경할 수 있는 볼륨이 주어집니다. 시작 볼륨에서 변경할 수 있는 볼륨을 더하고 뺀 값을 전부 확인하면 경우가 너무 많아집니다. 따라서 2차원 배열을 이용해 N번 째 볼륨을 바꿀 때, M번 볼륨을 만들 수 있는지를 확인하는 2차원 배열을 만들었습니..

문제 링크입니다. https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net N명이 사람이 있을 때, i번째 사람에게 인사를 하면 L[i]만큼 체력이 줄어들고, J[i]만큼 기쁨이 늘어납니다. 이때, 최대로 얻을 수 있는 기쁨을 구하는 문제입니다. 사람의 수가 따라서 확인할 수 있는 모든 경우를 확인했습니다. i번째 사람을 선택하는 경우와 안하는 경우가 있기 때문에 이를 모두 vector에 넣어준 뒤, 선택하는 경우에서 최댓값을 비교해주면 됩니다. 자세..

문제 링크입니다. https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 간단한 다이나믹 프로그래밍을 이용해 푸는 문제입니다. 몇일과 해당 날짜에서 먹은 떡의 개수가 주어질 때, 첫째, 둘째날에 떡을 몇개를 줬는지 구하는 문제입니다. 문제를 읽다보면 떡을 주는 갯수가 피보나치 수열과 같이 늘어나는 것을 볼 수 있습니다. 1일차 -> X, 2일차 -> Y개라고 한다면 3일차는 X + Y 4일차는 X + 2Y ... 이와 같은 방법으로 구해집니다..

문제 링크입니다. https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2차원 배열을 이용한 Dp로 풀 수 있는 문제입니다. 1, 2, 3을 통해 수를 만드는 경우의 수를 구하는 문제입니다. 수를 만들 때, 같은 수가 2번이상 중복되면 안됩니다. 따라서 수를 만들 때 마지막으로 더한 수를 저장해줘야합니다. -> 이를 2차원 배열을 통해 만들었습니다. [X][1~3]은 X의 수를 만들 때, 1~3의 수로 끝났다는 의미입니다. 따라서 K라는 수를 만들 수 있는 경우는 [K][1] = [K-1][2] + ..

문제 링크입니다. https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 2차원 다이나믹으로 풀 수 있는 문제였습니다. 1, 2, 3을 더함으로써 X라는 수를 만들 수 있는 경우의 수를 구하는 문제입니다. 중복된 경우를 없애는 방법은 오름차순으로서 경우를 관리하는 것입니다. 예를 들어, 1 + 1 + 2와 2 + 1 + 1을 오름차순으로 바꾸면 같은 경우가 됩니다. 모든 수의 합 경우를 저..

문제 링크입니다. https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1, 2, 3의 합을 통해 수를 만들 때, 경우의 수가 몇개가 나오는지 구하는 문제입니다. 같은 개수를 사용해도 위치가 다르다면 다른 경우로 봅니다. 예를 들어, 1 + 1 + 2와 2 + 1 + 1은 서로 다른 경우입니다. 1, 2, 3을 통해 만드는 것이기에 이전의 수들로 부터 +1, +2, +3을 한다면 수를 만들 수 있습니다. 만약, 7이라는 수를 만들려고 할 때, 6에 +1을 하면 됩니다. 그렇다는 것은 6의 경우의 수에..

문제 링크입니다. https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 부분 문자열의 개수를 구하는 문제입니다. 부분 문자열의 개수를 구하는 문제입니다. 문자열의 길이가 1 ~ N까지 있지만 1번 문자부터 마지막 문자까지 문자열을 만들어 가면 됩니다. 예를 들어, ababc의 경우 a에서 시작해 a -> ab -> aba -> abab -> ababc로 만들 수 있습니다. 다음은 b에서 시작해 b -> ba -> bab -> babc가 되며 다음은 a에서 시작해 a -> ab -> abc가 됩니다. 이를 계속 반복해서..

문제 링크입니다. https://www.acmicpc.net/problem/25314 25314번: 코딩은 체육과목 입니다 오늘은 혜아의 면접 날이다. 면접 준비를 열심히 해서 앞선 질문들을 잘 대답한 혜아는 이제 마지막으로 칠판에 직접 코딩하는 문제를 받았다. 혜아가 받은 문제는 두 수를 더하는 문제였다. C++ www.acmicpc.net 주어진 수를 4로 나눈 값만큼 long 을 출력하면 되는 문제였습니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #include using namespace std; int x; int main(){ cin.tie(0); cout.tie(0); cin >> x;..

문제 링크입니다. https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 주어진 수를 10진수로 바꾸는 문제입니다. ZZZZ는 36진수인데 이를 10진수로 바꾸는 과정은 Z * (36^(4-1)) + Z * (36^(3-1)) + Z * (36^(2-1)) + Z * (36^(1-1))가 됩니다. 다른 진법도 마찬가지로 바꾸는 방법은 같으니 이를 구현하면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #inc..

문제 링크입니다. https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 수를 뒤집에 같은 수만으로 만들 때, 최소 횟수를 구하는 문제입니다. 어려워보이지만 간단한 문제인데, 전체를 뒤집는다고 하면, 최소 횟수에 + 1을 더하는 행위나 마찬가지입니다. 따라서 0의 구역 갯수, 1의 구역 갯수를 구해 더 적은 갯수를 출력하면 됩니다. 예를 들어 0001100의 경우 0의 갯수는 2개, 1의 갯수는 1개임으로 1번만 뒤집으면 됩니다. 자세한 것은 코드를 ..

문제 링크입니다. https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 2진수를 8진수로 만드는 방법은 뒤에서부터 3개씩 끊어서 변경해주면 됩니다. 예를 들어 11001100의 경우 11 / 001 / 100 으로 나누어 각각 3 , 1 , 4로 만든 뒤, 이를 합쳐주는 과정입니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #include using namespace std; string x, y, ans; int main(){ cin.tie(0); ..