공부하자

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/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..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 코드 #include using namespace std; int N, M; int arr[9]; bool visited[9]; void dfs(int k){ if (k == M){ for (int i = 0; i M; dfs(0); } visited 배열은 0부터 시작해도 상관 없는데 arr에 저장할 땐 +1을 해줘서 1부터 N까지 자연수 중에서 중복 없이..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 퀸이 서로 공격할 수 없게 놓는 방법 : 같은 행 / 같은 열 / 같은 대각선 상에 위치하지 않아야 한다. (최지웅 교수님한테 배운 ㅎ) 생각 1. 백트래킹 문제니까 되추적 알고리즘을 쓴다 1.1. 상태 조건 트리를 어떻게 구성할 것인가? -> 트리까지 그릴 필요는 없는 문제인듯 아닌가 하하 1.2. promising 조건을 뭘로 할 것인가? -> 행 / 열 / 대각선이 겹치는지 확인하기 1차원 배열을 써도 되는..