본문 바로가기

BOJ/C++

 (202)
[BOJ] 사다리조작 1) 시간 초과를 조심 해야 한다. 2) 이건 개인적으로 유용해서 '질문 검색'에서 가져왔다. james_kylee 3일 전 테스트케이스가 대략적으로 몇개 나올지 생각해보면 됩니다. 대개 1초에 1억번 연산을 수행한다고 가정하는데, 경우의 수가 천만대 이하면 완전탐색을 하더라도 시간초과를 피할 수 있습니다. 반대로 1억개 이상의 경우의 수를 가진다면 완전탐색으로는 풀 수 없는 문제입니다. 이 경우에는 좀 더 최적화된 알고리즘이 필요합니다. 이 문제의 경우 사다리 수가 (대략적으로) 30 * 10 = 300개이며 1개, 2개, 3개를 선택하는 경우의 수는 300 + 300 * 299 / 2 + 300 * 299 * 298 / 6 < 5000000입니다. 500만개 이하의 경우의 수가 생기는데 이 정도면 충..
[BOJ] 배열 돌리기4 [문제] https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net [풀이] 17406 맞았습니다!! 2008 8 C++14 / 수정 2425 43초 전 0) 조합 + 단순 반복? 1)..
[BOJ] 안전영역 [문제] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net [풀이] 2468 맞았습니다!! 2208 16 C++14 / 수정 1200 58초 전 1) k보다 낮은 영역들은 사전에 방문표..
[BOJ] 분수의 합 [문제] https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net [풀이] 1735 맞았습니다!! 1988 0 C++14 / 수정 1100 35초 전 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 ..
[BOJ] 플로이드 [문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net [풀이] 11404 맞았습니다!! 2028 24 C++14 / 수정 934 35초 전 1) 제목부터 플로이드 와셜 알고리즘을..
[BOJ] 타임머신 [문제] https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net [풀이] 11657 맞았습니다!! 2396 8 C++14 / 수정 2343 10초 전 1) 한 정점에서 모든 정점을 돌면서 최단 경로를 찾으므로 다익스트라 or 벨만-포드 알고리즘을 사용한다. 하지만 타임머신을 사용해서 과거로 돌아가는 경우에는 음수 가중치가 있으므로 벨만-포드 알고리즘을 사용했다. 2) 벨만 포드 알고리즘은 최..
[BOJ] 최단 경로 [문제] https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicpc.net [풀이] 1753 맞았습니다!! 15732 108 C++14 / 수정 1763 2분 전 1) 하나의 정점에서 다른 모든 정점으로 ..
[BOJ] 게임개발 [문제] https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 1516 맞았습니다!! 2400 4 C++14 / 수정 1335 3분 전 1) 위상정렬 문제입니다. 2) 건물들의 우선순위가 주어지는데 원래 건물이 지어지는 시간을 잘 저장 해놔야한다. 이건 '질문하기' 에서 찾은 답변인데 딱 이해가는 설명입니다..

티스토리툴바