코딩 공부하는 코딩류

A에서 B로 만드는 데 필요한 최소 연산 횟수를 구하는 문제 문제의 조건 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 풀이 과정 처음엔 DP로 풀 수 있을까 해보다가... 각이 안 나와서 구글링 한 문제 ㅠㅠ 이 문제의 키포인트는 거꾸로 생각하는 것 이었습니다...!!!!! B에서 2로 나누거나 1을 빼고 10으로 나눠가며 A를 만들어 가면서 횟수를 세는 것이었죠... 즉 가능한 경우는 1..

수를 적절하게 묶어서 곱했을 때 구할 수 있는 최대 합계를 구하는 문제 문제의 조건 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 수열의 모..

0과 1로 이루어진 문자열을 몇 번 뒤집으면 모두 같은 숫자로 만들 수 있는지 구하는 문제 문제의 조건 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문..

강산이가 캠핑장에서 최대로 머무를 수 있는 일수를 구하는 문제 https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제의 조건 1. 강산이가 간 캠핑장은 연속된 P일 중에 L일만 머무를 수 있다. 20일 중에 10일만 머무를 수 있거나 8일 중에 5일만 머무를 수 있거나... 2. 강산이는 이제 막 V일짜리 휴가를 시작했다. 28일짜리 휴가를 시작했거나 15일짜리 휴가를 시작했거나... 3. 여러 테스트 케이스가 5(L) 8(P) 20(V) ..

N개의 숫자 묶음이 주어질 때 숫자 묶음들을 비교하려면 최소 몇 번만 비교하면 되는지 구하는 문제 문제의 조건 1. 정렬된 두 숫자 묶음이 있다. 두 묶음을 각각 A, B라 하면 두 묶음을 비교하는데 필요한 횟수는 A+B번이다. 2. 10장, 20장, 40장 처럼 2개보다 많은 숫자 묶음이 있을 때 2개씩 골라서 비교를 하는데 묶음들을 고르는 순서에 따라서 횟수가 달라진다. 10장과 20장을 먼저 합친 뒤(10+20=30), 남은 40장을 합치는 경우의 수를 더했을 때 (10+20)+(30+40)=100 총 100번의 비교가 필요하다. 하지만 10장과 40장을 합친 뒤(10+40=50), 남은 20장을 합치는 경우를 더하면 (10+40)+(50+20)=120 총 120번의 비교가 필요해서 100번보다는 ..

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 ..

가장 마지막 마을까지 가는데 필요한 최소 주유 금액을 구하는 문제 문제의 조건 1. 도시의 개수 N이 주어진다. 도시들은 일직선상에 있기 때문에 무조건 맨 앞 도시부터 차례대로 가야 한다. 2. 처음엔 차에 기름이 없기 때문에 맨 처음 도시에서 기름을 넣고 출발해야 한다. 기름통의 크기에는 제한이 없다. 도시 간 도로를 이용하여 이동할 때 1km당 1리터를 사용한다. 3. 각 도시에는 주유소가 하나씩 있으며 각 도시마다 기름 가격이 다를 수 있다. 그렇기 때문에 다른 도시보다 기름 가격이 싼 도시에서 최대한 넣고 가는 것이 이득이다. 4. 각 도시에 있는 주유소의 리터당 기름 가격과 각 도시 간 거리가 주어질 때 마지막 도시까지 가는데 필요한 최소 주유 금액을 구해서 출력하기 풀이 과정 처음엔 기름이 없..

자연수 N개의 수들의 합 S를 만들 수 있는 수들 중 N의 최댓값을 구하는 문제 문제의 조건 1. 수들의 합 S가 주어진다. 2. 자연수 N의 최댓값을 출력한다. 풀이 과정 첨 봤을 땐 뭐 이런 문제가 있나... 했는데 누적합계를 구하면서 나오는 최댓값을 구하면 되나 싶어서 누적합계를 구해 봤습니다. 근데 애매하게 틀린 숫자가 나오고 문제 자체도 이해가 잘 안 가서 힌트를 찾아봤습니다. 문제 이해 후 정리된 풀이 1. 누적합계를 구하는 방식으로 접근하는 것은 맞다. 2. 하지만 모든 수가 연속된 숫자일 필요는 없다. S = 5 라면 [1,1,1,1,1] 로도 5를 만들 수 있다. 이 경우엔 N개의 자연수 중 최댓값은 1이라고 할 수 있지만 유일하게 1만 있는 것이 아니다. 5를 만들기 위해서 1을 다섯번..