문제우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다..
알고리즘
문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.) 입력첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다. 출처:https://www.acmicpc.net/problem/2293 문제풀이동적 계획법 문제로 각 동전별로 for문을 돌린다1) 가장 첫번째 동전으로는 Dp[n]배열 안에 n을 만들수 있는 경우의 수를 넣는다. 예시인 1,..
문제N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.입력첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.출력입력으로 주어진 숫자 N개의 합을 출력한다. 출처: https://www.acmicpc.net/problem/11720 문제 풀이string으로 문자열을 받은뒤 for문으로 at()함수를 통해 하나씩 나누었다. 그 다음 0의 아스키 코드 값만큼 빼준 뒤 모든 숫자를 더하였다. 123456789101112131415#include#includeusing namespace std; int main(){ int N; cin>> N; string input; cin>>input; int sum=0; for(i..
문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 출처:https://www.acmicpc.net/problem/1463문제 풀이동적 계획법 문제로 간단한 문제이다각 n을 1로 만든느 최솟값을 Dp[n]이라고 하면 3으로 나누어 질때 2로 나누어 질때 그리고 나누어 지지 않을떄로 계산한다.1) 나누어지지 않으면 세번째 규칙을 사용하여 ..
2438번 별찍기-1 : https://www.acmicpc.net/problem/24382439번 별찍기-2 : https://www.acmicpc.net/problem/24392440번 별찍기-3 : https://www.acmicpc.net/problem/24402441번 별찍기-4 : https://www.acmicpc.net/problem/2441 for문을 이용한 간단한 기초 문제 별찍기 -112345678910111213#includeusing namespace std; int main(){ int N; scanf("%d",&N); for(int i=1;i
문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6개의 ..
문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 출력 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다 츨처:https://www.acmicpc.net/problem/2292 문제 풀이: -1까지는 1개의 방을 지나면 되고 7까지는 2개의 방..
문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/2667 문제 해결 과정: - 입력이 한줄씩 주어지므로 string으로 받아서 하나씩 나누어 map을 만든다- dfs를 사용하여 단지 번호를 붙인다.- map을 만..
