2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 처음에는 별생각없이 풀었고, 나중에 다들 map 을 쓴다는걸 알게되어서 추가하였다. 두가지 버전 모두 첨부한다. map(X) #include #include int main() { int N; bool visited[1000] = {false, }; std::vector input; std::vector output; std::cin >> N; std::string temp; // 입력 로직 for(int i = 0; i < N; ++i) { s..
Algorithm/BACKJOON
14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 해당 문제에 대해서 여러 풀이가 존재하지만, 이 풀이가 가장 좋아보이기에 주석을 달아 포스팅 해 본다. 해당문제에서 명심해야 할 점은 그냥 최고 급여만 출력하면 된다는 점이다. 날짜는 기록할 필요도 없다. 힌트는 '거꾸로' 계산하는 것이다. 예로 문제 내용을 보면 7일과 6일은 근무일을 넘어가기에 계산에 포함시켜야될 필요도 없다. 5일 = 15 O 4일 = 20 + 15 O 3일 = 10 + 20 + 15 O 2일 = 20 < (10 + 20 + 15) X 1일 = (10 + 20 + 15) == (10 + 20 + 15) O 따라서 최고로 나올 수 있는 값은 45 이다. 위 지식을 기반으로 아래 코..
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS, BFS 관련된 문제로 간단한 문제이다. 해석은 주석으로 기재 해 두었으며 코드의 흐름따라 주석과 함께 코드를 읽어보면 쉽게 이해가 될 것이다. #include #include // 이론상 정점의 개수는 1,000 개 이며 1 < N < 1000 이므로 1001 지정. // 간선의 개수는 10,000 개 미만임. // map 을 기준으로 1,000 x 1,000 = 1,000,000 의 간선 지정이 가능. #defin..
15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 n 과 m 을 입력받아.자연수 $1 \sim N$ 까지의 자연수 중 중복 없이 이뤄진 수열 $M$ 개를 도출한다. 설명이 조금 애매한데, 예제를 보면 쉽게 이해가 가능하다. 엄밀히 말해 $1 \sim N$ 까지의 자연수 중 $M$ 개로 이뤄진 수열의 '모든 조합' 을 찾는 것이다. #include int n, m; int arr[9] = { 0, }; bool visited[9] = { 0, }; void DFS(int cnt) { // cnt 와 m..
1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 내용은 한번 읽으면 모두 파악할 수 있을정도로 간단하다. 그런데 난이도는 골드 1 티어로 생각보다 높은편에 속한다. 1. 헤딩 #include #include int N; long long zero = 0; long long one = 0; long long two = 0; long long three = 0; long long four = 0; long long five = 0; long long six = 0; long long seven = 0; long long eight = 0; long long nine = 0;..
2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 이 문제는 생각보다 쉬운데, 난 많이 돌아서 풀었다. 신발끈 공식을 적용하지 않은 풀이 방법이다. 1. 그냥 풀어 보았다 #include #include #include struct Point { public: int x; int y; }; std::vector dots; int count; // 2차원 평면공간서 두 점의 거리를 구합니다. double getDistanceBetweenPoints(Point d1, Point d2) { return std::sqrt(std::pow((d2..
문제 설명 백준 1305번 문제는 다음과 같다. 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 문제에 관해 간략히 해설하자면, 흔히 보는 전광판에서 글자가 돌아가며 출력될 때, 특정 순간에 전광판을 포착했을 때 전광판은 특정 문자열로 구성되어 있을 터인데, 전광판 사이즈보다 글자 수가 적다면, 특정 글자가 반복될 것이다. 이 때, 최소 str.length() 가 얼마인지 return 하면 되는 간단한 문제이다....... 간단한 문제라고 생각했었는데, 생각보다 복잡하였다. 풀이 시행착오 이 문제의 경우 KMP 알고리즘에서 사..
19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 이전부터 비트마스킹에 대해서 좀 무시하는 경향이 있었다. 때문에 비트마스킹으로 처리할 수 있는 문제도 굳이 우회해서 처리하곤 했는데, 이번 문제에서 비트마스킹의 필요성을 느껴 배워서 코딩 하였다. 삽질 원래 필자가 생각했던 방법은 다음과 같다. 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 ..
1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 정말 간단한 문제이다. 논리적으로 조금만 생각해 보면 어렵지 않게 풀 수 있다. 설명 위 문제의 키포인트는 '마지막 자리' 숫자만 출력하면 된다는 것이다. 위의 예제입력 9 635 의 경우엔 9의 635 제곱을 하라는 의미인데, 이런식으로 연산하는것은 자원 낭비가 심할뿐더러 추가 라이브러리를 이용하지 않는다면 overflow 를 일으킬 것이다. 마지막 자리만 구하기 위해서는 굳이 모든 연산을 할 필요가 없다 코드 #include using namespace std; int..
2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 벌집 문제로 이전에 했던 투포인트보다 논리적으론 조금 어려운 문제이다. (나는 투포인트 문제가 더 쉬웠다) 설명 문제는 비교적 직관적으로 이해하기 쉬운 편이다. 위와 같이 벌집이 있을때, 벌집을 자세히 관찰 해 보면 특정 숫자 구간마다 경로가 증가하는것을 확인할 수 있다. 위 선을 기준으로 벌집의 경로가 하나씩 증가한다. 7 의 경우엔 = 1,7 → 2 8 의 경우엔 = 1,2,8 or 1,7,8 → 3 육각형 내의 경로점을 그려보면, 같은 육각형 내의 선분이 지나가는 ..
