반응형 백준45 BOJ 10448 - 유레카 이론 / C++ 문제 링크 : https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 풀이 자연수 k의 범위는 1000까지이고 삼각수의 공식은 n * (n + 1) / 2 이므로 44 * 45 / 2 = 990, 탐색 범위는 n = 44까지 하면 된다. 삼각수를 저장하는 vector를 하나 생성하여 1부터 44까지의 n * (n + 1) / 2 를 원소로 넣는다. 3중 반복문으로 삼각수들을 더하며 n을 만들 수 있는지 체크하는 함수도 생성해준다. n을 만들 .. 2023. 11. 26. BOJ 11728 - 배열 합치기 / C++ 문제 링크 : https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 주어지는 두 배열은 이미 정렬되어 있는 상태이므로 각 배열의 0번째 인덱스부터 비교하여 순서대로 출력하면 된다. 한 포인터라도 크기를 벗어나면 while문이 종료되므로 나머지 포인터도 증가시키며 값들을 출력하면 된다. 코드 #include #include using namespace std; int main() { ios_base::sync_.. 2022. 6. 14. BOJ 14502 - 연구소 / C++ 문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 벽 3개를 세울 수 있는 경우의 수는 DFS로 완전탐색하고 그렇게 생성된 배열을 다시 BFS로 순회하며 바이러스를 퍼뜨리고 안전 영역을 세야한다. 우선, 입력 받은 배열을 돌며 0(빈 칸)을 발견하면 해당 지역부터 DFS를 시작한다. 해당 지역에 벽(1)을 세우고 DFS 카운트를 늘려준 뒤 다시 배열을 돌며 다음 0(빈 칸)을 찾는다. 이렇게 DFS의 카운트가 3이 되면 벽을 모두 세웠으므.. 2022. 5. 4. BOJ 14501 - 퇴사 / C++ 문제 링크 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 문제의 형태 덕분에 DP로 풀이해야한다는 것은 쉽게 감이 오지만 점화식을 세우기는 어렵다. 먼저 i일에 할 수 있는 행동을 생각해보면 1. Ti 만큼의 날짜를 소요하여 Pi를 획득한다. 2. 그냥 i+1로 건너뛴다. 1번 경우에는 DP[i + Ti] + P[i] = DP[i]가 될 것이고 2번 경우에는 DP[i + 1] = DP[i]이 될 것이다. 따라서, DP[i]에 대한 점화식을 DP[i] = max(DP[i + Ti] + P[i], DP[i + 1])로 세울 수 있다. 하지만, 이렇게 점화식을 세우려면 DP[.. 2022. 5. 4. 이전 1 2 3 4 ··· 12 다음 반응형
