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 1+3 (3+1) 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 접근법 이전의 만들 수 있는 방법의 수에 그 다음 수가 추가 되었을 경우 만들 수 있는 경우의 수를 추가하는 방식으로 진행한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..
https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 문제 접근법 단순 이동만이 아니라 물이 매턴마다 차오르는것을 신경써야 하는 문제이다. 주어진 맵을 그리기 위한 2차원 배열 1개와 물이 차오..
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 문제 접근 방법 이동 가능한 3가지 방법에 대하여 진행을 해야 한다. 이동 경로에 대한 저장이 필요하므로 경로에 대한 배열을 추가..
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 문제 접근 방법 BFS를 이용하여 풀 수 있는 문제임을 확인한다. 이동 가능한 케이스를 3가지에 대해 모두 진행하여 정답을 찾으면..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 접근 방법 1차원 배열과 2차원 배열 하나를 준비한다. 1차원 배열에는 칠판에 적은 N개의 수를 하나씩 저장한다. 주어진 2개의 숫자를 가지고 해당 배열의 방값을 서로 비교하여 같은 지 체크한뒤 같다면 2차원 배열에 해당 값들은 서로 같다는 표시를 하고 작은 방 배열은 다음 배열 방으로 큰 방 배열은 이전 배열 방으로 이동하여 반복한다. 틀릴 경우 바로 0을 출력한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11..
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 접근 방법 필요한 연산을 어떻게 진행할 방법을 생각한다. bit연산을 사용하면 빠르게 문제를 풀 수 있으므로 bit 연산을 채택 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 5..
https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. www.acmicpc.net 문제 접근 방법 부등호를 기준으로 값을 비교하면서 조건에 맞으면 문자를 더하는 형식으로 진행 문자가 특정 자릿수가 되면 vector에 집어넣어준다 0부터 시작하므로 vector 내부에 최초 값이 최소 값이고 마지막 값이 최대값임을 인지하고 진행 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 접근 방법 기간과 비용에 대한 vector를 만들고 그곳에 값을 넣어둔다. 첫날부터 시작하여 일을 하는 경우와 일을 하지 않는 경우로 나뉘어 계산을 진행한다. 계산하여 이전값보다 큰값이면 갱신한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include using namespace std;..
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 접근 방법 입력 받은 문자들을 오름차순으로 정리한다. 원하는 암호의 길이가 될 때까지 공백에서 한문자씩을 더한다. 원하는 길이가 되었을 때 모음과 자음 갯수를 만족하는지 체크한다. 조건이 성립하면 문자를 출력한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34..
https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2 www.acmicpc.net 문제 접근 방법 vector를 두개를 만들고 하나는 빈 상태로 유지 하나는 고른 숫자들을 집어 넣는다 비어 있던 vector에 숫자를 하나씩..
