알고리즘 (14) 썸네일형 리스트형 [백준 11060] 점프 점프 www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 이문제는 DP 개념을 이용해서 여러개의 경우의 수 중 도착에 가까운 순부터 최적의 경우를 메모리에 저장하는 방식으로 문제를 풀었다. // 점프 점프 #include #define MAX_N 1000 using namespace std; int g_nMap[MAX_N]; int g_nDP[MAX_N]; int Jump2End(int N, int nPos) { if(g_nDP[nPos]!= 0) { re.. [백준 2231] 분해합 www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 이문제는 최대로 더해 질 수 있는수가 999999 로 9*6인 54이다. 그래서 54보다 작은 수에서 시작해서 brute force로 탐색해서 풀면 된다. 코드는 다음과 같다. //분해합 #include #include using namespace std; int main(void) { int n = 0; int nAns = 0; int nLen = 0; string strTmp; .. [백준 19598] 최소 회의실 개수 www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 입력으로는 각 회의별 시작시간과 끝나는 시간이 들어온다 최소한 사용할 수 있는 회의실로 겹치지 않게 끔 빌리는게 우리가 해야할 일이다. 그래서 나는 시작시간을 기준으로 sorting 을 하고 하나씩 가져와서 기존에 저장한(시작은 없음) 회의실 vector에서 원소랑 비교를한다 첫번 째 예로 들면은 입력 0 40 15 30 5 10 sorting 0 40 5 10 15 30 비교시작 1 ///////// 처음.. [백준 4848] 집합 숫자 표기법 www.acmicpc.net/problem/4848 4848번: 집합 숫자 표기법 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있고, 집합 숫자 표기법으로 나타낸 수가 주어진다. 두 수의 합은 항상 15보다 작거나 같다. www.acmicpc.net 이문제는 숫자가 15까지 밖에 없어서 모든 수의 집합에 관련된 문자열을 string 배열에 담은뒤 문자열과 매치 되는 수를 구하고 그 수의 합을 다시 string으로 반환해서 얻어내는 과정으로 했다. 코드는 다음과 같다. //집합 숫자 표기법 #include using namespace std; int main(void) { int T = 0; string DP[16]; string str1; string str2; ci.. [백준 16953] A > B www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B #include using namespace std; int A2B(int A, int B, int nCnt) { if(B == A) return (nCnt + 1); else.. [백준 11729] 하노이 탑 이동 순서 www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이 탑의 규칙성을 찾으면 금방 풀 수 있는 문제이다 (과거에 수업에서 이문제를 배운 기억이 있었지만 다 까먹어서 생각하는데 애를 좀 먹었다..ㅎㅎ) 규칙을 설명드리면 다음과 같아 예시) 4인 경우 1 2 3 4 ---------- a b c 1위의 모든 블록을 3으로 옮길때 이를 나눠서 생각하면 4개의 블록을 옮기는 테스크를 크게 3개로 나눠볼수 있다 1 2 3 ---------- a b c a.. [백준 2979] 트럭 주차 www.acmicpc.net/problem/2979 2979번: 트럭 주차 첫째 줄에 문제에서 설명한 주차 요금 A, B, C가 주어진다. (1 ≤ C ≤ B ≤ A ≤ 100) 다음 세 개 줄에는 두 정수가 주어진다. 이 정수는 상근이가 가지고 있는 트럭이 주차장에 도착한 시간과 주차장� www.acmicpc.net 이문제는 고정된 크기로 입력이 들어오기 때문에 배열의 크기나 입력등을 고정적으로 두었다. 문제에서 유의할점은 1대일때 1대당 A가격 2대일때 1대당 B가격(B*2) 3대일때 1대당 C가격(C*3) 으로 1대당 가격을 잘 생각해야한다. 그리고 시간이라는 것도 참고해야한다.(ex 1~6 = 5시간) 그래서입력으로 들어온 길이만큼 배열을 1로 바꾸고 다음 반복문에서 배열 0 1 2 에서 1인 원.. [백준 16504] 종이접기 www.acmicpc.net/problem/16504 16504번: 종이접기 종이접기와 수학을 좋아하는 주성이는 종이접기와 수학을 한꺼번에 할 수 있는 놀이를 찾아냈다. 바로 N×N 크기를 가지는 색종이의 각 칸에 수를 적어놓고, 색종이를 반으로 접을 때마다 겹치는 www.acmicpc.net 이문제도 규칙만 알면 쉽다 예시에서 2x2로 예시를 들었는데 이를 생각해보면 모든 원소를 더한 값과 동일한 것을 알 수 있다. 그래서 들어오면 바로 다 더해주는 방식으로 문제를 풀었다. #include using namespace std; int main(void) { int N = 0; long long Ans = 0, Tmp = 0; cin >> N; for(int i = 0; i < N; i++) { for(.. 이전 1 2 다음
