공부하자

https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 정리 주어진 아이들의 키를 가장 적게 움직여서 증가수열이 되도록 정렬하는 문제 문제가 왤케 쓸데없이 길어;;; 난독 오게 생ㄱ김 생각 DP로 푸는데 아이의 위치를 변경할 때마다 그 때까지의 최대 증가수열의 길이를 저장 코드 #include #include using namespace std; int main() { int N; cin >> N; int children[N]; int dp[N]; fo..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 정답 코드 #include #include using namespace std; int main() { int N, arr[300], stair[300], dp[300] = {0}; cin >> N; for(int i=0 ; i> arr[i]; } for(int i=0 ; i

https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 간단한 정답 코드 #include using namespace std; int main() { long S, sum = 0, result = 0; cin >> S; for (int i = 1; sum S; long result, start = 0, end = s; while(start

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 생각 1. 배열 세 개 만들어서 두 개는 입력받고 한 개는 몇 개 가지고 있는지 계산해서 출력 2. 쉽긴 한데 배운 걸 써먹어 보자면! 비교를 할 때 정렬 후 이분탐색으로 비교하면 시간이 더 줄어들 것 같으니 이 걸 써보자! 정렬은 상근이가 가지고 있는 숫자카드를 정렬하면 될 듯 정답 코드 #include #include using namespace std; i..

https://www.acmicpc.net/problem/5622 5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net 생각 abc는 3초 / def는 4초 / ghi는 5초… 알파벳을 입력 받고 해당하는 초 누적으로 더해서 출력해주기 알파벳 인식을 어떤 식으로 해야되나 고민! 1. if문이나 switch문으로 돌린다 2. 아스키코드를 사용한다 ( 형변환 사용!) 나는 2번으로 풀었다! 1. 입력 받은 문자열의 인덱스 하나하나를 검사한다! 2. 여기서 (int)형변환을 사용해서 숫자로 변경한다 3. -65(대문자 A의 아스키코드 값)를 해주고 3으로 나누어준다 ex) A : (65-65)/3 = 0..

https://www.acmicpc.net/problem/2903 2903번: 중앙 이동 알고리즘 상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. www.acmicpc.net 생각 규칙이 있나? 답이 전부 제곱수인 건 알겠다! 0 - 2^2 1 - 3^3 2 - 5^5 3 - 9^9 4 - 17^17 5 - 33^33 … 2, 3, 5, 9… 이 숫자들을 전 단계의 제곱수를 만들기위한 n이라 하면 output은 n*(n-1)이 된다! 빠르게 코드 작성을 해보자 정답 코드 #include using namespace std; int main(){ int n, n..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 생각 1. 이건 knapsack 문제다! 동전이니까 자르지 못하는 knapsack 문제 2. 근데 그렇게 어려운 고민 할 필요 없이 단순하게 금방 풀 수 있는 문제다! 알고리즘 구상하지 않고 빠르게 풀 수 있음 정답 코드 #include using namespace std; int main(){ int n,k; cin >> n >> ..

https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 보자마자 생각난 것 : color graph! 알고리즘 수업 열심히 들은 보람이 있다고 생각했다 ㅋㅋㅋ 교수님 보고 계십니까?!! 앞으로 엘베에서 마주치면 90도로 인사박겠습니다!!! 하하 암튼 나한테 휴학은 없으니까 내년 그니까 3학년 1학기 시험기간이 돌아올 때 까지 1일 1백준 다시 레츄고 애들아 열심히 하자... 생각 행운의 문자열인지 확인하는 방법 (Find 함수로 따로 만들자!) 1. 인접한..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net + C++의 next_permutation 함수를 사용하면 더 쉽게 풀 수 있다! 하지만 난 안 썼음 생각 1. 계산하고 비교하면서 큰 것만 남긴다! 근데 진짜 어떻게 해야할지 모르겠어 배열의 크기 제한이 8까지니까!! 작으니까 뭔가 하면 될 것 같아 코드 초안 int N, ans; int arr[9]; int result(){ // 일케 계산하는 함수를 따로 만들고! int result = 0; for(int..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 나 난독 있나봐... 생각 숫자가 들어가는 경우 / 안들어가는 경우로 나눠 dfs를 돌리자 1. sum += arr[1]; 2. sum = sum; 코드 초안 약간 이런 느낌 void dfs(int k, int sum){ for(int i=0 ; i main에서 S가 0일때만 공집합을 하나 빼주자~ 2. if 처리를 어떻게 해야할지 모르겠음!!! -> 그냥 fo..