연잎의 develog

20946번: 합성인수분해 (acmicpc.net) 20946번: 합성인수분해 수열 $A = a_1, a_2, \dots, a_n$가 수열 $B = b_1, b_2, \dots, b_m$보다 사전 순으로 앞선다는 것의 엄밀한 정의는, 다음 중 하나를 만족한다는 것이다. $a_1=b_1,\ a_2=b_2,\ \dots,\ a_{i-1}=b_{i-1}$이고 $a_i < b_i$인 $i$가 www.acmicpc.net [문제] [해결전략] 어떤 수 N을 *소인수 분해한 결과가 다음과 같다고 하자 N =P1 x P2 X P3 X P4 ... 우선 에라토스테네스의 체를 이용해 소인수 분해하는 방법은 알튜비튜 동적계획법 역추적에서 배웠었다! prime dp배열에 각각의 수들이 어떤수의 배수로 지워졌는지를 저장해두고..

20943번: 카카오톡 (acmicpc.net) 20943번: 카카오톡 카카오톡은 주식회사 카카오가 2010년 3월 18일 서비스를 시작한 글로벌 모바일 인스턴트 메신저로, 2020년 기준 $4\,000$만 명의 사용자가 등록돼 있고 시장 점유율이 $96$%로 사실상 거의 모든 국민 www.acmicpc.net [문제] [해결전략] 처음에 조합을 이용해서 전체 경우의 수를 구하고, 기울기가 같은 직선들을 map 에 저장해서 만날 수 없는 직선들의 경우의 수를 하나씩 빼내가는 알고리즘을 생각했었다. 그리고 시간복잡도가 최악인 코드가 탄생했다. #include #include #include #include using namespace std; typedef pair ci; map ..

22991번: 수요응답형 버스 (acmicpc.net) 22991번: 수요응답형 버스 현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호 www.acmicpc.net [문제] 배차 요청을 하는 그룹들이 N 개가 있는데, 현재 M 개의 수요응답형 버스가 운행중이다. 이 때, 문제에 나온 것처럼 최대한 많이 배차 요청들을 각각의 버스에 매칭을 시켜줘야 하는 것이 이 문제의 목표입니다. [해결전략] 이 문제에서는 배차 시간과 인원 수 라는 2가지의 변수를 함께 고려해야 한다. 그러나, 2가지 변수를 한번에 고려하는 것은 복잡하기 때문에, 하나의 변수를 고정시켜두고..

22986번: Flat Earth (acmicpc.net) 22986번: Flat Earth 각 테스트 케이스별로 테스트 케이스가 주어진 순서대로 지구의 끝에 도달할 수 있는 칸의 수를 한 줄에 출력하여 총 $T$줄에 걸쳐 출력한다. www.acmicpc.net [문제] [해결전략] 1. 자동차는 1초에 2칸씩 움직이고, 지구는 1초에 1칸씩 커진다. 따라서 자동차를 이용하면 지구의 끝과의 거리를 1초에 1씩 줄여나갈 수 있다. . 따라서, 줄일 수 있는 거리는 최대 K 이며 출발 칸과 지구의 끝과의 거리가 K 보다 크다면 지구의 끝에는 도달할 수 없다. 지구의 크기가 N 일 때, 지구의 끝과 거리가 K 보다 큰 칸들은 크기가 N − K − 1이었을 때의 지구이다. 따라서, 답은 크기가 N 일 때의 지구..

22981번: 휴먼 파이프라인 (acmicpc.net) 22981번: 휴먼 파이프라인 모든 상자를 최대한 빠르게 옮기는 경우의 작업 시간을 분 단위로 출력한다. www.acmicpc.net [문제] [해결전략] 브루트포스 방식으로 N을 두팀으로 나눌 수 있는 경우의 수를 모두 구해서 총 시간을 계산해 제일 빨리 끝나는 경우의 시간을 갱신시키려는 원초적인 방법을 1초동안 생각하고 바로 집어넣었다. N이 최대 200,000 이기 때문에 ! N을 두 팀으로 나눌 수 있는 경우의 수는 거의 N의 부분집합의 개수인 2 ^ (200,000)에 육박한다..ㅎㅎㅎ 주어진 작업속도 vi를 오름차순으로 정렬한 것을 a1, a2, · · · aN 라고 해보자 1. 모든 사람이 두 팀중 하나엔 들어가야 하기 때문에 두팀 중 ..

문제집: N과 M (시리즈) (acmicpc.net) 문제집: N과 M (시리즈) www.acmicpc.net 오늘은 N과 M (시리즈 ) 를 통해 순열, 조합, 중복순열, 중복 조합을 연습해보려고 한다! 1. N과 M (1) : 순열 (nPm) 을 구하는 간단한 문제! [풀이] #include #include #include using namespace std; int n, m; int check[9] = { false, }; int pArr[8] = { 0, }; void permutaion(int depth) { if (depth == m) { for (int i = 0; i < m; i++) { cout num[i]; } sort(num, num + n); //오름차순 정렬 permutaion(0..

[C++] 순열(Permutation) 조합(Combination) 알고리즘 :: 개발 블로그 (tistory.com) [C++] 순열(Permutation) 조합(Combination) 알고리즘 백준에서 완전 탐색 문제를 풀다가 항상 조합과 순열을 만들 때 헷갈려서 아예 시간을 내어 정리하였다. 이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다. 이후 나오는 hongchan.tistory.com 브루트 포스 문제를 풀다보면 거의 순열 or 조합 의 연장선인 경우가 많다! 오늘은 c++ 로 순열과 조합을 어떤식으로 구현할 수 있는지 정리해보려고 한다. 1) 순열 (nPr) 서로 다른 n개 중 순서를 고려하여 서로 다른 r 개를 뽑는 경우. (순서O, 중복X) 중복을 막기위해 ch..

2961번: 도영이가 만든 맛있는 음식 (acmicpc.net) 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net [문제] 재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램 [해결전략] N(1 ≤ N ≤ 10) 이므로 재귀 + 브루트포스로 조합할 수 있는 모든 경우의 수를 해보아도 무방! DFS 탐색의 인자로 cnt(몇번째 재료를 선택하는 갈림길에 있는지) , sour( 신맛의 곱) , salty(짠맛의 합)을 넘긴다. 이때, 재료를 사용했는지 여부..

14620번: 꽃길 (acmicpc.net) 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net [문제] [해결전략] 조합을 활용하면 되는 문제이다! N(6≤N≤10) 이므로 3번의 재귀호출 동안 꽃을 심을 위치(100가지 좌표)를 정해도 100 * 100 * 100 = board.size() || ny = board.size()) //벽에 가로막힌다면 //return false; if (board[nx][ny]) //무언가 이미 심어져 있다면 return false; } return true..

16508번: 전공책 (acmicpc.net) 16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net [문제] [해결전략] 가지고 있는 전공책의 개수 N이 (1 ≤ N ≤ 16) 이므로 16개 각각의 전공책을 선택할지말지로 케이스를 분류하면 최대 2^(16) 가지의 경우의 수가 나온다. 재귀 + 브루트 포스로 문제를 해결하면 될 것 같다. 그리고 타겟스트링에 존재하는 모든 글자를 얻었다면(재귀탐색의 끝), 최소 비용을 갱신해준다. 이때, 한번 사용중인 글자가 중복해서 사용되는 걸 방지하기 위해 선택된 문자열은 공백(' '..