본문 바로가기

전체 글

 (47)
BOJ 1461 도서관 백준 BOJ 1461 도서관 C++ https://www.acmicpc.net/problem/1461 1) 단순 시뮬레이션 문제 2) 조건 "책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. " 를 이용해서 왼쪽/오른쪽 통틀어서 가장 큰 절댓값을 가진 위치를 마지막에 이동하는 것으로 생각하여 ans에 더한다. 3) 그 외 값들은 책을 두고, 다시 원점 0으로 돌아와야 하기 때문에 leftLoc[]에서 인덱스가 가장 큰 것의 배열값X2(왕복)을 ans에 더한 후, M만큼 인덱스를 감소했다. 마찬가지로 오른쪽(rightLoc[])도 인덱스가 큰 값에서부터 확인하여 ans에 더한 후, M만큼씩 인덱스를 이동했다. 4) 위치가 담긴 배열의 인덱스를 적절히 조작해서 계산하는 재미있는 문제였다. /..
BOJ 1517 버블 소트 백준 BOJ 1517 버블 소트 C++ https://www.acmicpc.net/problem/1517 1) 문제의 N제한이 50만이기 때문에, O(N^2)은 TLE이다. → 문제 이름은 '버블 소트'이지만 "합병 정렬"을 이용하여 풀어야 한다. 2) 합병 정렬 수행시, 원소의 위치가 변경 될 때 그 거리를 count 한다. 3) 합병 정렬을 다시 구현해보고 복습할 수 있는 문제였다. // no bubbleSort, yes mergeSort #include #include using namespace std; int N; int a[500005]; int b[500005]; long long ans=0; void merge(int start, int mid, int end){ int i = start;..
BOJ 14442 벽 부수고 이동하기 2 백준 BOJ 14442 벽 부수고 이동하기 2 (C++) https://www.acmicpc.net/problem/14442 1) BFS 문제이다. 2) 에서 벽을 부술 수 있는 갯수인 cnt의 조건만 변경하면 쉽게 풀 수 있다. /** * 200519 * BOJ 14442 벽 부수고 이동하기 2 * BFS */ #include #include using namespace std; int N, M, K; int map[1005][1005]; int check[1005][1005][11]; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int cnt=0; int bfs(int x, int y){ queue q; q.push(make_pair( make_pair(x,y), 0..
BOJ 11057 오르막 수 https://www.acmicpc.net/problem/11057 - DP - 3중 for문 - 예외처리 : 길이가 1일 때 #include int d[1005][11]; int mod = 10007; int main(){ int n; scanf("%d", &n); // 길이가 1인 경우 처리 for(int i=0; i
BOJ 10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 - DP - d[] : 길이가 n인 계단 수 - 예외처리 할 것이 늘어남! : 길이가 1일때 : 길이 2이상일 때 - 모든 0과 9에 대하여 #include int d[102][10]; long long int mod = 1000000000; long long ans=0; int main(){ int n; scanf("%d", &n); for(int i=1; i
BOJ 2193 이친수 https://www.acmicpc.net/problem/2193 - DP - DP는 쪼갠다! - 수의 범위를 보고 자료형을 잘 선택하자! : 피보나치의 46항 이상이 되면 int로 표현할 수 없다. #include long long int d[95]; int main(){ int n; scanf("%d", &n); d[0]=0; d[1]=1; for(int i=2; i
BOJ 11052 카드 구매하기 https://www.acmicpc.net/problem/11052 - DP - 입력으로 주어진 가격을 저장하는 배열 a[] - d[] : 구해야 할 것 - 이중 for문을 이용해야 해서 헷갈렸다. : d[i]를 구할때마다 1~i까지 중 최댓값을 계속 비교해야한다 #include #include using namespace std; int a[1010]; //주어진 것 int d[1010]; //구할 것 int main(){ int n; scanf("%d", &n); for(int i=1; i
BOJ 9095 1,2,3 더하기 https://www.acmicpc.net/problem/9095 - 역시 DP 문제 - 점화식만 찾으면 거의 풀었다고 볼 수 있는데 점화식 찾기가 어렵다.. - 이 문제에서는 테스트 케이스 갯수가 주어지기 때문에 d[]를 모두 구하고 필요한 것만 출력하였다. #include int d[12]; int main(){ int cnt,n; scanf("%d", &cnt); d[0]=1; d[1]=1; d[2]=2; for(int i=3; i

티스토리툴바