2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 오랜만에 다시 푼 이진탐색 문제 입국심사 loop invariant에 대해 알고난 뒤에는 탐색 범위 설정에 유의하고 나니 설계도 더 명확하게 되고 잘 풀리는 느낌이다 대부분의 이진탐색에서 공통적으로 적용되는 조건인 left < right를 제외하면, 이 문제에서는 left일 때에는 모든 사람이 통과하는 것이 불가능하고 right일 때 에는 모든 사람이 통과하는 것이 가능해야 한다. ..

https://www.acmicpc.net/problem/21941 21941번: 문자열 제거 지우고 싶은 문자열 $S$와 지울 수 있는 문자열 $A_{1}$, $A_{2}$, ..., $A_{M}$이 주어진다. 문자열 $A_{i}$들은 각자 $X_{i}$라는 점수를 가진다. 이 때, 문자열 $S$를 삭제 연산을 이용하여 모두 제거하려 www.acmicpc.net 아주 고생고생고생한 DP문제 첫 번째 접근: 원래 문자열에서 해당하는 문자열을 삭제하고 중간 문자열들에 대한 최대 점수를 DP로 저장하는 방식(🔥시간초과🔥) import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline def func(origin): global d,cache if len(..

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 오늘 깔끔하게 프로그래머스 미로탈출 푸는게 목표였는데.... ^^흠 DP는 항상 어렵다 특히 for문을 잘 쓰는 bottom-up 방식은 생각이 안 난다 그래서 나는 항상 재귀함수를 구현한 뒤에 메모이제이션을 적용한다 DP는 어렵다 . . . #include #include using namespace std; int T, W; int plum[1005], cache[2][31][1005]; int fun..

https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 토스 코테에서 활용해야 했다고 했던 sorted map을 유의하고 푼 문제 string으로 문자열을 입력받아서 map에 저장한 뒤 각각의 비율을 출력해주는 간단한 문제엿다 파이썬으로 풀고싶었는데 개수 제한 없이 입력받는 법을 아직 모르겠다 ㅠ #include #include #include using namespace std; map m; int main() { char str[35];..

https://www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 다익스트라를 이용해서 풀었지만 거리의 누적 합의 최소를 찾는 것이 아닌 경로 중 최소값 만을 요구하는 문제였다 그래서 맨 처음 입력을 받은 뒤 모든 나무의 좌표를 큐에 넣은 뒤 BFS를 수행하여 모든 정점으로부터 나무까지의 거리를 구했고 다익스트라를 수행하면서 선택할 수 있는 다음 좌표 중 (나무와의 거리)가 가장 큰 좌표를 선택하게 했다 시간초과가 엄청 많이 났는데 .. 그 이유는 무식하게 모든 나무 좌..

https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 운영체제 CPU 스케줄링 알고리즘인 라운드-로빈을 구현하는 문제 현재 점유중인 손님의 time quantum이 종료됨과 동시에 손님이 들어왔을 때 처리가 잘못 된 것인지 .. 계속 틀렸다 ㅠ 1주 4문제 실천중인데.. 1일 1문제 풀어야 하나 ❓❓ ㅎㅎ 코딩하기 정말 힘들다 ~~ #include #include #include using namespace std; typedef struct..

https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 이분탐색 + DFS로 풀거나 다익스트라로 풀 수 있는 문제 나는 다익스트라로 풀다가 계속 맞왜틀 발생해서 그냥 이분탐색 + DFS로 풀었당 ㅎㅎ #include #include #include #include #define ll long long using namespace std; int map[1001][1001], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, n; bool visit[1001][1001]; bool safe(int x, int y) { return x >= 0 &..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 현재 볼륨이 범위에 적합하지 않는 경우(불가능)일 때와, 아직 계산하지 않은 경우(가능 여부 모름)일 때를 분리해주어야 한다는 걸 시간초과 덕분에 알았다 #include #include using namespace std; int n, s, m; int v[101], cache[101][1001]; int dp(int cur, int dep) { if (cur..