'백준' 태그의 글 목록 (4 Page)

2021. 10. 29. 21:22 Algorithm/BOJ

문제 링크 http://icpc.me/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 덱을 이용하여 풀 수 있다. 덱에 들어있는 값을 단조적으로 유지하면서 k번째 값이 들어올 때 그 k번째 값이 덱에서 가장 큰 값을 유지하게 덱을 관리하면 된다. 또한 덱에는 k - l - 1 이후에 들어온 값만 있어야 한다. 덱을 위와 같이 관리하면 덱의 제일 앞에 있는 값이 최솟값이 되게 된다. cf) 세그먼트 트리를 이용하면 O(nlogn)에 풀 수 있을 것 같지만 상수 때문..

백준[5430] AC

2021. 10. 29. 17:43 Algorithm/BOJ

문제 링크 http://icpc.me/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 덱을 이용하여 풀이 할 수 있다. 배열을 뒤집을 때, 진짜로 배열을 뒤집게 된다면 이때 시간복잡도가 O(n)이기 때문에 O(np)가 되어 터지게 된다. 그렇기 때문에 배열을 뒤집었는지 여부를 체크하여 수를 앞에서 버릴지 뒤에서 버릴지 정해야한다. 코드 #include #include #include using namespace std; void solve() { deque dq; string cmd; cin >> cmd; int n; cin >> n; string i..

백준[16234] 인구 이동

2021. 10. 29. 14:32 Algorithm/BOJ

문제 링크 http://icpc.me/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 dfs를 이용한 구현 문제다. bfs로 풀어도 똑같을 것 같다. 문제의 조건에 주어진대로 모든 점을 순회하면서 연합이 생기는지 확인하고 연합이 생긴다면 그 점들의 인구를 평균으로 바꿔주면 된다. dfs를 순회하면서 연합이 되는 점들을 스택에 담아 두었다가 순회가 끝나고 스택에 있는 점들을 모두 평균으로 바꿔주는 방식으로 구현했다. cf) 반복문에서 재귀를 호출할 때 retuen dfs(); 와같이..

백준[1676] 팩토리얼 0의 개수

2021. 10. 28. 14:28 Algorithm/BOJ

문제 링크 http://icpc.me/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 0의 개수를 구하기 위해서는 n! = k * 10^a에서 a를 구하면 된다. 이때 10을 만들기 위해서는 5와 2가 필요한데 n!에서 2의 개수는 항상 5의 개수보다 많기 때문에 n!에서 5의 개수를 구하면 된다. 코드 #include int main() { int n; scanf("%d", &n); int ret = 0; while (n) { ret += n / 5; n /= 5; } printf("%d", ret); }

백준[20208] 진우의 민트초코우유

2021. 10. 27. 17:22 Algorithm/BOJ

문제 링크 http://icpc.me/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 풀이 끔찍한 민트초코의 최대 개수가 10개이기 때문에 백트레킹으로 전탐색을 하면 된다. 이때 집에 다시 돌아올 수 있는것을 고려해줘야 하는데, 남은 체력보다 집까지의 거리가 더 클 때 최댓값을 갱신해주면 된다. 구현을 할때는 dfs를 하듯이 모든 점을 움직이면서 탐색한다면 나올 수 있는 경로가 매우 많아 시간이 터지고 민트초코가 있는 위치를 저장해놓은 후에 그 점들 사이에서만 움직여야 한다. 코드..

백준[1037] 약수

2021. 10. 26. 16:36 Algorithm/BOJ

문제 링크 http://icpc.me/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 풀이 짝이 되는 두 수를 찾아 서로 곱하면 원래의 수가 나오기 때문에 가장 작은 수와 가장 큰 수를 곱하면 된다. 코드 #include #include using namespace std; int arr[52]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", arr + i); sort(arr, arr + n); prin..

백준[1270] 전쟁 - 땅따먹기

2021. 10. 22. 12:30 Algorithm/BOJ

문제 링크 http://icpc.me/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n n / 2) printf("%lld\n", idx); else printf("SYJKGW\n"); } }

백준[23247] Ten

2021. 10. 20. 11:24 Algorithm/BOJ

문제 링크 http://icpc.me/23247 23247번: Ten A real estate company IC is managing a rectangular section of land. The section is divided into $mn$ segments in $m \times n$ matrix shape, where the number of rows and that of columns are $m$ and $n$, respectively. Each segment has its own price as a posi www.acmicpc.net 풀이 2차원 누적합을 이용하는 문제다. 2차원 누적합을 모른다면 2차원 누적합 설명을 참고해라. 모든 경우를 확인하며 넓이가 300이 되는 경우를 찾으면 ..

백준[20168] 골목 대장 호석 - 기능성

2021. 10. 20. 01:27 Algorithm/BOJ

문제 링크 http://icpc.me/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 풀이 백트레킹을 이용하여 풀 수 있다. n의 크기가 매우 작으니 백트레킹을 하며 모든 경우를 확인해보면 된다. 코드 #include #include using namespace std; int d[11][11]; int n, m, a, b, c, ans = 1e9, totalSum = 1e9; bool visited[11]; void solve(int cur, int total, i..

백준[2729] 이진수 덧셈

2021. 10. 19. 17:46 Algorithm/BOJ

문제 링크 http://icpc.me/2729 2729번: 이진수 덧셈 이진수 덧셈은 매우 간단하고, 십진수 덧셈과 비슷하게 하면 된다. 십진수 덧셈을 할 때는, 오른쪽부터 왼쪽으로 차례대로 숫자 하나씩 더하면 된다. 이진수 덧셈도 이와 비슷하게 하면 된다. 십 www.acmicpc.net 풀이 구현만 잘하면 되는 문제다. 수를 더할 때 맨 뒤에서부터 더하기 때문에 구현의 편의를 위해 입력받은 이진수를 둘 다 뒤집고 앞에서부터 연산하며 정답이 될 수의 앞부터 채워나갔다. 그런 후 최종 정답은 reverse를 했다. 그리고 문제 조건에 앞에 불필요한 0이 붙으면 안 된다는 조건 때문에 출력을 1을 발견했을 때부터 하고, 만약 다 끝까지 1이 발견되지 않는다면 값이 0이기 때문에 0을 출력한다. 이 부분을 ..

백준[1374] 강의실

2021. 10. 16. 22:40 Algorithm/BOJ

문제 링크 http://icpc.me/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 풀이 이 문제는 관찰을 잘한다면 풀 수 있다. 모든 수업에 대해서 시작하는 시간과 끝나는 시간을 정렬해서 가지고 있을 때, 만약 지금 보는 수가 수업이 시작하는 수라면 필요한 강의실이 하나 더 필요할 것이다. 반대로 지금 보고 있는 수가 끝나는 시간이라면 필요한 강의실이 하나 줄어들 것이다. 예를 들어, 1~4까지 하는 수업과 2~5까지 하는 수업이 있고 이 수들을 정렬하여 1 2 4 5라는 수를 가지..

백준[18429] 근손실

2021. 10. 16. 13:30 Algorithm/BOJ

문제 링크 http://icpc.me/18429 풀이 3대 500을 찍고 싶은 헬창이라면 누구나 풀어봐야 할 루틴을 정하는 문제이다. 백트레킹으로 모든 경우를 확인하며 풀 수 있다. 코드 #include #include using namespace std; vector v; int n, k, ans; bool visited[10]; void solve(int cur, int sum) { if (sum < 0) return; if (cur == n) { ans++; return; } for (int i = 0; i < n; i++) { if (visited[i]) continue; visited[i] = true; solve(cur + 1, sum + v[i] - k); visited[i] = false;..

백준[16507] 어두운 건 무서워

2021. 10. 15. 15:10 Algorithm/BOJ

문제 링크 http://icpc.me/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 2차원 누적합으로 풀 수 있다. 누적합을 이용하지 않고 푼다면 주어진 쿼리를 모두 확인하는 방식으로 푼다면 O(RCQ)로 10억이 넘어가 시간이 터질 것이다. 그렇기 때문에 누적합을 이용하여 쿼리당 O(1)에 구간 합을 구해야 한다. psum [i][j] : 오른쪽 아래 꼭짓점이 (i, j)에 있을 때 내부에 있는 밝기의 합이라고 할 때, psum [i][j]는 ..

백준[3015] 오아시스 재결합

2021. 10. 15. 02:37 Algorithm/BOJ

문제 링크 http://icpc.me/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 스택을 이용하여 풀 수 있다. 이 문제는 i번째 사람이 1 ~ i -1번째 사람 중에서 몇 명을 볼 수 있는지 확인하면 된다. 여기서 잘 관찰을 해보자면 i번째 사람이 볼 수 있는 사람은 자기보다 큰 사람에 막히지 않은 사람들이다. 그렇다면 사람들을 자기보다 큰 사람이 앞에 있어 볼 수 없는 사람과 볼 수 있는 가능성이 있는 사람들로 나눌 수 있다. 그럼 이제 가능성이 있는 사람들만 가지..

백준[14428] 수열과 쿼리 16

2021. 10. 14. 14:16 Algorithm/BOJ

문제 링크 http://icpc.me/14428 풀이 세그먼트 트리 문제다. 세그먼트 트리에 최솟값을 저장할 때, 인덱스도 포함하여 저장하면 된다. cf) 나는 min도 구현을 해서 사용했지만, stl에 있는 min()을 그냥 사용해도 된다. 코드 #include #include using namespace std; using pii = pair; int arr[100005]; pii tree[400005]; pii min(pii &a, pii &b) { if (a.first < b.first) return a; if (a.first == b.first) { if (a.second < b.second) return a; else return b; } else return b; } pii query(int..

티스토리툴바