그린푸딩

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net dp[i]를 i일 바로 전까지 일해서 얻을수 있는 최댓값이라 하면 1) i-1일까지 일해서 얻는 비용 2) i-1일에는 일 안하지만 그 이전에 어느 구간에 일한 구간 이 두가지 경우 중에 더 큰값을 dp[i]에 넣어주어야 한다. 어렵다.. #include #include #include using namespace std; vectorarr; vectordp; int..

https://school.programmers.co.kr/learn/courses/30/lessons/118667# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에 큐로 풀었는데 잘안풀려서 힌트를 조금 봤더니 투포인터로 풀린데서 풀었는데 시간초과가 났었다. 투포인터로 푸는방법은 1. 큐를 이어 붙여서 하나의 벡터에 추가해준다. 2. 한쪽 포인터는 맨앞에, 뒤쪽 포인터는 기존 하나의 큐 크기의 위치에 놓는다. 3. 그러면 앞쪽 큐를 pop한다고 치면 앞쪽 포인터를 뒤로 움직이고,뒤쪽 큐를 pop하면 뒤쪽 포인터를 뒤로 움직여주면 된다. 처음에 시간초..

#include #include #include using namespace std; vectorA; int curr, curc; int dr[4] = { 0,1,0,-1 }; int dc[4] = { -1,0,1,0 }; //격자 밖으로 나간 모래의 양 int ans = 0; int N; int dx[4][10] = { {-1,1,-2,2,-1,1,-1,1,0,0},{0,0,0,0,-1,-1,1,1,2,1},{-1,1,2,-2,1,-1,1,-1,0,0},{0,0,0,0,1,1,-1,-1,-2,-1} }; int dy[4][10] = { {0,0,0,0,1,1,-1,-1,-2,-1},{-1,1,-2,2,-1,1,-1,1,0,0} ,{0,0,0,0,-1,-1,1,1,2,1} ,{1,-1,2,-2,1,-1,..

https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기www.acmicpc.net 문제풀때 주의해야할점 1. 새로운 구름 위치를 표시할때 예를들어 (4,1)->(1,1) (1,1)>(2,1) 이처럼 이동할때 (4,1)을 배열에서 값을 0으로 만들고 (1,1)을 1로 바꾸는것처럼 알고리즘을 짜면 뒤에서 (1,1)->(2,1)에서 새로 갱신해서 1로 있어야할 값을 0으로 바꿔버린다. 그래서 그냥 새로운 배열을 만들고, 다시 기존 배열에 복사하는게 낫다. 다른 답안안보고 풀어서 ..

DP는 쉬워보이는데 막상 구현하면 꽤어렵다. 이문제에서 헷갈렸던 부분은 다음 dp값을 갱신을 n+1날짜가 넘어걸때는 해주지말아야하는데(if(i+t1[i]>n+1)continue;) 현재 dp값을 갱신하는건 넘어가던지 상관없이 했어야하는데 이부분의 위치를 잘못설정해서 틀렸었습니다가 떴었다. #include #include #include #include using namespace std; int main() { vectordp; int n; cin >> n; vectort1; t1.assign(n+1, 0); vectorp1; p1.assign(n+1, 0); for (int i = 1; i > t1[i] >> p1[i]; } dp.assign(n+2, 0); //최대 수익 출력하기 int m = 0; ..

문제를 보고 백준 2468번 구역을 구하는 dfs 문제가 생각났다. 각 구역의 넓이(갯수)를 좀더 창의적으로 구해보고 싶은데 나중에 시도해봐야겠다.. 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 #include #include using namespace std; vectorvisited; int dr[4]={0,0,-1,1}; int dc[4]={-1,1,0,0}; int m1,n1; int ..