전체 글 (168) 썸네일형 리스트형 BOJ A +B 문제집 풀이 의도 백준 온라인 저지(이하 BOJ)는 문제의 입력과 출력을 표준 입출력으로 처리하도록 되어있다. A + B 문제집을 통하여 다양한 입출력 포맷을 해결하고, 표준 입출력과 친해지자. 본문에서 다룰 문제 목록 BOJ A + B 문제집 출처 문제 번호 제목 BOJ 1000 A + B BOJ 2558 A + B - 2 BOJ 10950 A + B - 3 BOJ 10951 A + B - 4 BOJ 10952 A + B - 5 BOJ 10953 A + B - 6 BOJ 11021 A + B - 7 BOJ 11022 A + B - 8 BOJ 15740 A + B - 9 A + B 피연산자 2개가 빈 칸을 사이에 두고 한 줄에 입력된다. 결과를 출력한다. C 해법 scanf("%d%d", &A, &B); pri.. 백준 2503 숫자 야구 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다. www.acmicpc.net 가능한 모든 경우의 수에서 소거해나가기 /* 1. ball은 strike를 제외한 경우를 생각할 것 */ /* 2. 문제 잘 읽기 -> 서로 다른 수를 힌트로 제공 */ #include #include #include #include using namespace std; int N; queue q; string hint, candidate; int .. 백준 16568 엔비스카의 영혼 16568번: 엔비스카의 영혼 첫째 줄에 N, a, b가 주어진다. (0 ≤ N ≤ 1,000,000, 0 ≤ a, b ≤ N) www.acmicpc.net 두 풀이 방법의 메모리 시간차가 엄청나다... // Tabulation - Bottom Up #include #include using namespace std; int N, a, b; int dp[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> a >> b; for (int i = 1; i = 0) { dp[i] = min(dp[i], dp[i - a - 1] + 1); } if (i - b - 1 >= 0) { dp[i] = min(d.. 백준 5719 거의 최단 경로 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 최단경로를 찾아 포함된 간선을 모두 제거해야 한다. 따라서 삭제가 O(2 * N)인 벡터 기반 인접 리스트 (x) 삭제가 O(1)인 인접 행렬 (o) 대신 다익스트라에서 u와 인접한 v를 찾는 연.. 백준 11779 최소비용 구하기 2 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시 www.acmicpc.net inf = |V| * max(weight) = 1억 경로 기록 v의 기존 경로보다 u를 경유하는 것이 더 빠를 때 v의 경로를 u 경유로 수정 & v의 부모를 u로 갱신 경로 출력 dst v.. 백준 1238 파티 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net 다익스트라 2회 수행 각 마을에서 출발해 X에 도착 각 간선의 방향을 반전시킨 후 X에서 출발하는 다익스트라 수행 X에서 출발해 각 마을에 도착 두 거리의 합의 최댓값이 정답 #include #include.. BOJ 16457 단풍 이야기 16457번: 단풍잎 이야기 첫째 줄에 키의 개수 n, 퀘스트의 개수 m, 퀘스트 당 사용해야 하는 스킬의 수 k가 주어진다. n은 10 이하, k는 n 이하의 양의 정수이며, m은 100 이하의 양의 정수이다. 둘째 줄부터 m개의 줄에는 각각의 퀘스트에서 사용해야 하는 스킬들이 나온다. 스킬들의 이름은 1에서 2n까지의 정수로 주어진다. www.acmicpc.net 퀘스트를 나타내는 방법(자료구조) 처음에는 배열을 생각했다. 하지만 선택된 스킬로 퀘스트를 수행할 수 있는지 비트 연산만으로 파악할 수 있도록 비트마스크로 퀘스트를 나타내기로 했다. 조합을 탐색하는 방법(알고리즘) 브루트포스(재귀) 브루트포스로 2n개의 스킬 중 n개 선택 m개의 퀘스트 중 수행할 수 있는 개수 계산(동일) O(C(2n, n.. 배열로 만든 벡터 초기화할 때는 별도로 만든 배열 크기 자료구조만 0으로 만들어 주면 끝 어짜피 배열 크기만큼만 참조하기 때문에 배열 크기 초기화로 끝! SWEA 무선 충전 이전 1 2 3 4 ··· 21 다음
