본문 바로가기
  • Let's study

PS/백준56

[C++] 백준 1520: 내리막길 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해결방법 dfs와 dp를 사용해서 풀 수 있는 문제이다. dp[x][y]에 저장되는 값은 (x, y)에서 (n-1, m-1)까지 가는 방법의 개수이다. 제일 왼쪽 위 (0,0)에서 현재 위치의 값보다 작은 방향으로 이동하면서 d[x][y] += dfs(nx,ny) 식을 통해 dfs를 돌려 다음 위치의 dp값을 받아오면 된다. 코드 #include using namespace std; int n, .. 2023. 10. 8.
[C++] 백준 19637: IF문 좀 대신 써줘 문제 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 해결방법 특정 값이 아닌 범위를 찾는 것임을 기억하고 있어야 한다. 출력할 수 있는 칭호가 여러 개일 경우 가장 먼저 입력된 칭호 출력해야 하므로 입력받은 값 X가 mid번째 칭호의 전투력보다 작거나 같으면(x < v[mid].second) right=mid-1을 해준다. 이 외에는 left=mid+1을 해준다. 위에서 X와 칭호의 전투가 같았을 때.. 2023. 10. 6.
[C++] 백준 1238: 파티 문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해결방법 다익스트라 알고리즘으로 풀 수 있다. 1부터 N까지 각 노드를 출발지로 하는 최단거리를 구한 후, X를 목적지로 하는 최단 거리를 배열에 저장한다. X를 출발지로 하고 1부터 N까지의 최단 거리를 구한 후, 1에서 구한 배열에 더해준다. 배열에 각 인덱스에 저장된 값은 노드 -> X + X -> 노드 값이다. 따라서 가장 큰 값을 출력해주면 된다. 코드.. 2023. 10. 4.
[C++] 백준 25828: Corona Virus Testing 문제 https://www.acmicpc.net/problem/25828 25828번: Corona Virus Testing Testing for Corona can be done individually, e.g., 100 people require 100 test kits. Alternatively, the test can be done in groups (pools), e.g., 100 people can be divided into five group of 20 people each and then using only one test kid per group. If one www.acmicpc.net 해결방법 그룹별 검사하는 데 사용되는 키트 수는 그룹 수 + 그룹별 인원수 * 양성인 그룹 수이고 .. 2023. 5. 22.
[C++] 백준 25881: Electric Bill 문제 https://www.acmicpc.net/problem/25881 25881번: Electric Bill The first input line contains two integers (each between 2 and 20, inclusive), indicating the rate/KWH for the first 1000 KWH and the rate/KWH for the additional usage, respectively. The next input line contains a positive integer, n, indicating the number www.acmicpc.net 해결방법 입력받은 고객의 에너지 소비량에서 1000은 기본 요율, 1000을 뺀 나머지는 추가 요율을 적용하여 .. 2023. 5. 21.
[C++] 백준 9772: Quadrants 문제 https://www.acmicpc.net/problem/9772 9772번: Quadrants Given the coordinates (x,y) of some points in 2-dimensional plane, find out which quadrant(Q1-Q4) the points are located. If a point is located on X-axis or Y-axis, print out AXIS instead. www.acmicpc.net 해결방법 x와 y가 양수인지 음수인지로 어느 사분면인지 출력하고 축이면 AXIS를 출력한다. 마지막 0 0일 때도 AXIS를 출력해야 한다. 코드 #include using namespace std; int main() { ios_base::s.. 2023. 5. 20.