2JINISHAPPY 2JINISHAPPY

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..

https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 값의 범위를 신경써야 하는 다익스트라 문제 정점은 10000개라서 인접행렬을 만들 시 10000*10000=1억개 * 4byte의 메모리가 필요한데 간선이 최대 10만개 들어오므로 꼭 인접리스트로 처리해야 한다 #include #include #include #define ull unsigned long long #defin..

https://www.acmicpc.net/problem/22114 22114번: 창영이와 점프 창영이는 버스에서 내린 뒤 회사로 걸어가고 있다. 창영이가 걸어가는 길은 대부분 회색 보도블럭으로 포장되어 있는데, 가끔씩 빨간 보도블럭이 놓여있을 때가 있다. 창영이는 어린 시절 빨간 www.acmicpc.net 오랜만에 푸는 DP문제 처음에 bottom-up으로 풀려고 했는데 점화식이 계속 생각이 안 나서 재귀로 푼 다음에 메모이제이션 적용했다 dp도 재귀(top-down)이기 때문에 base case, inductive step, memoization 이 세 가지 위주로 설계해야 할 듯 #include #include using namespace std; int n, k, l[100005], dp[2][..