목록전체 글 (217)
Study hard
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 [풀이] 2020/09/14 - [백준/DP] - (c++)백준 14501번: 퇴사 (c++)백준 14501번: 퇴사 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i]: i번째 날 상담하면 그 이후부터 최대로 받을.. nim..
www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i]: i번째 날 상담하면 그 이후부터 최대로 받을 수 있는 이익 상담이 끝나는 날이 N+1보다 커지면 무시한다. #include #include //max using namespace std; int N; int T[16]; int P[16]; int DP[16] = { 0, }; void solution() { int ans = 0; for (int i = N; i >= 1; i--) { //상담이 끝나는 날이 N+1보다 크면 if (i + T[i] > N + 1) continue; else { in..
www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net [풀이] DP로 풀 수 있는 문제! DP[i] : i번째 칸에서 최소 몇 번 점프해야 N번째 칸에 갈 수 있는지 주어진 칸이 한 칸일 경우, 한 번만 점프해서 N번째 칸에 갈 수 있는 경우, 점프할 수 없는 칸인 경우를 모두 신경써줘야 한다. #include #include //memset using namespace std; int N; int Maze[1001]; int DP[1001]; vo..
www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net [풀이] 진행할수록 범위가 좁아지므로 DP를 사용한다. 어느 방향에서 와야 값이 커지는 지 확인 점화식 DP[i][j] = Maze[i][j] + max(DP[i-1][j], max(DP[i][j-1], DP[i-1][j-1])) #include #include //max using namespace std; int N, M; int Maze[1001][1001]; int DP[1001][1..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [풀이] 1. bfs사용 2. 사다리나 뱀이 있는 칸은 LorS배열에 해당 칸에 도착하면 어느 칸으로 이동하는지를 저장했다. 3. visited배열을 사용하여 한 번 방문했던 칸에 대해서는 다시 탐색하지 않도록 했다.(안 하면 메모리 초과!) #include #include using namespace std; struct Pos { int x; in..
https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net [풀이] bfs를 사용했다. 연산의 아스키 코드 순서대로 queue에 푸시해주었기 때문에 값이 t가 되면 바로 그때까지 했던 연산들을 출력하면 된다. set자료구조에 나온 값을 저장하여 같은 값에 대해 더 이상 탐색하지 않게 했다. /연산으로 인해 나오는 1은 처음 한 번만 나오면 되므로 set을 탐색하지 않고 boolean값으로 사용 여부를 체크했다. 사실 -는 쓸일이 없다. (t는 항상..