2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 이모티콘이 생겼다 택배 문제는 모든 정점에서 모든 정점으로의 최단 거리 및 최초 경유지를 구하는 문제이다 다익스트라와 플로이드와샬 두가지 방법 아무거나 사용해서 해결할 수 있다 map[i][j] = k -> i번 집하장에서 j번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 k번 집하장으로 이동해야 한다 라고 할 때, distance가 갱신되는 시점에 해당 값을 update해주면 된다 #includ..

www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 비트마스킹의 정석같은 문제 BFS로 출구를 탐색해야 하지만 최대 6개의 문과 열쇠가 있기 때문에 열쇠의 소지 정보를 비트로 표현해서 탐색 정보로 활용해야 한다 #include #include #include #include using namespace std; typedef struct { int x, y; }point; int n, m, dx[] = { 1,0,-1,0 }, dy..

www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 오늘부터 제일 싫어하는 위인 1위: 다익스트라 일요일 아침의 데이트 문제는 좌표를 빈칸 / 쓰레기 칸 / 쓰레기 근처 칸으로 분류해서 최대한 쓰레기 근처를 피해서 목표 지점까지 도달해야 하는 문제이다 처음에 보았을 때는 좌표에 가중치를 두면 되겠다 -> 그러면 쓰레기 칸은 2 & 쓰레기 근처 칸은 1 정도로 놓으면 되겠지?라고 생각했는데 틀렸다 극단적으로 생각하면 형택이는 쓰레기 근..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 카카오 기출에 슬라이딩 윈도우를 이용한 문제가 종종 등장하길래 풀어본 투포인터 기초 문제 left, right 두 개의 포인터를 배열의 양 끝에 위치하도록 한 뒤 (left 포인터를 한 칸 이동한 것 vs right 포인터를 한 칸 이동한 것) 중 절댓값이 더 작은 쪽으로 이동하게끔 구현했다 n=int(input()) w=sorted(map(int,input().split())..

www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/problem/..

www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 오랜만에 풀어보는 투포인터 문제! 투포인터는 보통 최적의 해를 갖는 특정 구간을 찾아내는 문제에서 많이 사용한다 이 문제는 중복되지 않는 원소의 개수를 최대로 하는 k개의 연속된 구간을 찾아내는 문제이당 (+쿠폰 사용을 위해 쿠폰 번호 element 또한 포함되어 있는지 확인) 예제에서는 그림과 같이 [2, 7, 9, 25]에 보너스로 30까지 포함한 5가 정답이 된..

www.acmicpc.net/problem/17951 17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야 시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다. www.acmicpc.net 스터디할 때 풀었던 문제인데 왜 답이 right일까?를 고민하다가 이제 이유를 알아냈다 이진탐색 및 매개변수 탐색의 진행에는 loop-invarient라는 성질이 적용된다. loop를 지속하게 하는 절대적인 조건이므로, loop가 시작되기 전 & loop 중 & loop 이후에도 정해진 loop-invarient는 유지되어야 한다. 이 문제(parametric search)에서는 parameter를 "각각의 그룹에 속한 시험지 점수의 합 S 중 최소값을..

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 내가 기존에 못 하던 유형인 DP, 이진탐색을 연습할 필요성을 느껴서 간간히 풀어보려고 한다 대표적인 문제인 나무자르기 사실 옛날에는 봐도 감이 안 와서 몇번을 풀려고 트라이했지만 실패했었는데 스터디에 이진탐색 빡고수분의 지도를 몇 번 받아 이제 감이 슬슬 오고있따 이진탐색 문제는 left, right 변수를 설정하는 것이 가장 핵심인 것 같다. 처음부터 이진탐색 솔루션이..