연잎의 develog

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [문제] [해결전략] 만일 n이 그다지 크지 않았다면, 백트래킹과 같은 방식으로 O(2^N)만에 해결이 가능하지만 지금 처럼 N이 300일때는 어림도 없다 따라서 DP 를 통해 해결해주어야한다. 1. 테이블 정의하기 dp [i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값 만일 위와 같이 테이블을 정의하게 되면 연속한 세계단을 모두 밟을 수 없다는 제약조건을 점화식에 넣을 방법이 없다..! 따라서 테이블을 다른 방식으로..

2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [문제] [해결전략] 1. blank 벡터에 빈칸좌표를 pair 형태로 모두 담는다. 2. dfs 로 idx(몇번째 빈칸을 처리하고 있는지) 를 넘겨주면서 빈칸을 하나씩 채워나간다. 이때 유효하지 않는 값이 채워지면 재귀가 더 깊숙히 수행되지 않도록 백트래킹을 활용한다. 이때 빈칸에 해당 숫자가 들어가도 되는 지 확인하기 위해 check (row,col,num) 함수를 이용한다. 이 함수는 (row.col)에 num ..

19575번: Polynomial (acmicpc.net) 19575번: Polynomial 경근이는 수학을 좋아한다. 수학을 너무 좋아하는 나머지 다항식을 빠르게 평가하는 프로그램을 작성했다. 미지수 x로 구성된 다항식 f(x)에서 x에 k를 대입하여 f(k)를 구하는 것을 평가라고 한다 www.acmicpc.net [문제] [해결전략] [풀이] #include #include using namespace std; const int MOD = 1e9 + 7; int solve(int n,int x, vector coef) { long long ans = coef[0] ; for (int i = 1; i > n>> x; vector coef(n+1, 0); int degree; for (int i = 0..

문제집: N과 M (시리즈) (acmicpc.net) 문제집: N과 M (시리즈) www.acmicpc.net 오늘은 N과 M (시리즈 ) 를 통해 순열, 조합, 중복순열, 중복 조합을 연습해보려고 한다! 1. N과 M (1) : 순열 (nPm) 을 구하는 간단한 문제! [풀이] #include #include #include using namespace std; int n, m; int check[9] = { false, }; int pArr[8] = { 0, }; void permutaion(int depth) { if (depth == m) { for (int i = 0; i < m; i++) { cout num[i]; } sort(num, num + n); //오름차순 정렬 permutaion(0..

14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [문제] [해결전략] nn을 설정하고 그때의 profit값을 활용해 최대 수익을 갱신해준다. [풀이] #include #include using namespace std; typedef pair ci; int max_profit=-1; //최대수익 void consult(int n,int profit,int day, vector consulting) { //총 일수, 수익,현재 날짜, 상담 정보 if (day > n) //n일차를 넘어서면 { max_profit = max(max_profit, profit); // 최대 수익 갱신. return; } if ..

17626번: Four Squares (acmicpc.net) 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net [문제] 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램 [해결전략] 1. 재귀탐색 제곱수들을 배열에 저장해놓고, 1 3 9 16 25 36 49 64 재귀함수이용(최대 depth = 4)해서 4개의 정수를 뽑자. 그런데 n의 범위를 살펴보니 1 ≤ n ≤ 50,000 이고 제곱급취하면 225니까 1~ 4개의 정수를 뽑는 경우의수는 ..

5430번: AC (acmicpc.net) 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net [문제] [해결전략] 구분자를 바탕으로 문자열을 나누고 숫자형태로 덱에 저장. 명령이 R인지 D인지 구분하고, -> R(reverse)은 함수를 따로 만들어 호출. D는 pop_front. -> 이렇게 풀면 시간초과 나네요 하하ㅏㅎ 그래서 방향을 바꿨습니다! 함수 R에서 꼭 배열을 뒤집지 않고도 뒤집은 효과를 낼 수 있죠! 바로 덱을 이용하면 가능합니다. 만일 1234라는 값이 입력으로 들어왔다고치면 아래와 같은 상태일겁니다. 그리고 원래 제가 생각했던 방식대로 RDD를 한다..

2015번: 수들의 합 4 (acmicpc.net) 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net [문제] [해결전략] 🔰방법 1. v[0] + v[1] +v[2]...v[n-1] v[1] + v[2] ...v[n-1] .. v[n-2] + v[n-1] 바깥포문 -> i를 포함해서 만들 수 있는 부분합. 안쪽포문 -> j가 i+1 ~ N 까지 돌면서 수를 더해감. 이때 값을 하나 더할때마다 K가 되는지 확인하고 맞다면 cnt++ int su..

1946번: 신입 사원 (acmicpc.net) 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [문제] [해결전략] 1. 지원자들을 우선 서류심사성적이 높은 순서대로 나열한다. 2. 이제 자신보다 서류성적이 높은 사람들에 대해 면접성적이 높은지만 확인해주면 된다. ex. 서류순위 2등인사람은 서류순위 1등인사람의 면접순위 점수보다 높다면 신입사원으로 뽑힐수있다. (서류순위 3등,4등 ...과의 면접순위는 비교하지 않아도됨 . 이미 서류순위가 높기때문.) ex. 서류순위 4등인사람은 서류..

13458번: 시험 감독 (acmicpc.net) 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net [문제] [해결전략] 감독관 수를 저장하는 변수 cnt선언. 각 시험장 별 응시자의 수를 담는 배열을 만들고 입력받는다. 그후 1. 각 시험장 인원수에서 총 감독관이 담당할수있는 학생수(B)를 빼주고 cnt++; 만일 인원수 > n; int* A = new int[n]; //각 시험장에 있는 응시자의 수를 저장할 배열 동적할당. for (int i = 0; ..