분류 전체보기
-
[백준] 1202번 보석 도둑문제 풀이 2020. 8. 2. 18:21
1202 보석도둑 문제세계적인 도둑 상덕이는 보석점을 털기로 결심했다.상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)모든 숫자는 양의 정수이다. 출력첫째 줄에 상덕이가 훔칠 수 있..
-
[백준] 10986번 나머지 합문제 풀이 2020. 8. 1. 13:56
10986 나머지 합 문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이)update 쿼리가 없고, 구간 합만 구해서 나머지를 확인하면 되는 문제라segment tree 가 아니고 prefix sum 을 이용한 문제다.그리고 모든 ..
-
Prefix sum알고리즘 2020. 8. 1. 12:34
Prefix sum (구간합) Algorithm - 구간 합이란? 배열 전체 값 중 L ~ R 번째 원소 구간의 합을 의미 - 구현 방법 : Prefix sum algorithm은 데이터 원소들을 누적해서 합한 값을 이용한다. a1, a2, ..., aN 전체 N개의 숫자들이 있을 때 prefix sum의 i번째 값을 구하면 Pi = a1 + a2 + a3 + ... + ai ex) 숫자 5개가 있다고 하자. {1,2,3,4,5}; 그러면 prefix[6] = {0,1,3,4,10,15}; 만약 1번째부터 3번째까지 합을 구하고 싶다면 : prefix[3] - prefix[1-1] = 4 - 0 = 4 이런식으로 계산. => prefix sum의 차로 구간합을 계산한다. L ~ R까지 합을 구하고 싶으면..
-
[백준] 17780번 새로운 게임문제 풀이 2020. 7. 31. 18:31
17780 새로운 게임 문제) https://www.acmicpc.net/problem/17780 풀이)시뮬레이션 문제이다. 선언한 자료들① 말의 정보를 저장하는 구조체를 선언 & 정보 저장 배열 선언struct horse {int y, x, dir; // 말의 위치, 방향 }; vector h_info; ② 체스판의 상태를 나타내는 int map[12][12]; 선언③ 체스판의 위치에서, 가장 아래쪽에 있는 말 번호를 저장하는 int horse_map[12][12]; 선언 만약 (1,1) 자리에 1 - 3 - 4번 순으로 말들이 쌓여있다면horse_map[1][1] = 1이다. ④ 각 말들이 업고? 있는 말 정보 저장하는 vector parent[10]; 선언 만약 1 - 3 - 4 순으로 말들이 쌓여..
-
[백준] 6087번 레이저 통신문제 풀이 2020. 7. 30. 18:42
6087 레이저 통신 문제크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다. 입력첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 10..
-
[백준] 9328번 열쇠문제 풀이 2020. 7. 29. 20:46
9328 열쇠 문제상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다'.'는 빈 공간을 나타낸다'*'는 벽을 나타내며, 상근이는..
-
[백준] 5213번 과외맨문제 풀이 2020. 7. 28. 19:46
5213 과외맨 문제) https://www.acmicpc.net/problem/5213 풀이)어려운 문제는 아니였는데 몇가지 사항을 간과해 계속 틀렸던 문제이다.한 번 꼬이기 시작하니깐 문제 조건들을 자세히 읽지 못했다. 과정은 이러하다.1. 타일들을 N * (N*2) 배열에 둔다고 생각하자. //map[N][N*2] 입력 예시로 보면 (N=5) 2. 배열의 각 칸마다 현재 칸의 값과 이 칸이 어떤 타일에 속하는지, 그리고 이 칸을 방문했었는지 정보를 저장하는 구조체를 저장해둔다. struct Tile_info{int val, int number, bool visited; }; //구조체를 이용해 배열 map선언 => Tile_info map[N][N*2] 위의 입력 예시그림을 참고로 보면 // map..
-
[백준] 1504번 특정한 최단 경로문제 풀이 2020. 7. 27. 15:49
1504 특정한 최단 경로 문제방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 ..