본문 바로가기

분류 전체보기

 (124)
백준 1697번 숨바꼭질 (c++) +1, -1, *2 로 탐색하는 경우에 대해서 BFS로 문제를 풀어주면 된다. Queue에는 해당 위치와 몇번만에 도착했는지를 pair로 저장해서 넣어주고, 목적지에 도달했을 때, pair에 저장되어 있는 값을 확인해주면 된다. #include #include using namespace std; bool visited[100010]; int main() { for (int i = 0; i > n >> k; queue q; pair start = make_pair(n, 0); q.push(start); visited[n] = true; int answer = 0; while (!q.empty()) { pair..
백준 1012번 유기농 배추 (c++) BFS문제입니다. 모든 지역을 방문하고, 배추가 있는 지역에 방문했을 때, BFS로 연결되어있는 모든 지역을 다 방문합니다. 배추가 있는 지역을 처음 방문할 때의 횟수를 정답으로 출력해주면 됩니다. #include #include using namespace std; int hatake[55][55]; bool visited[55][55]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int m, n, k; bool isSafe(int x, int y) { if (x >= 0 && x = 0 && y > t; while (t--) { cin >> m >> n >> k; for (int i = 0; i < n; i++) { for (int j = 0; j..
백준 17626번 four squares (c++) 어떤 수를 제곱수의 합으로 표현할 때, 사용되는 최소 제곱수의 개수를 구하는 문제이다. 다이나믹 프로그래밍으로 문제를 해결할 수 있다. n = (0, 1, 2, 3, ... n -1) + k2(k는 k2 > n; dp[0] = 0; dp[1] = 1; for (int i = 2; i
백준 11049 행렬 곱셈 순서 행렬의 곱셈 순서에 따라서 필요한 곱셈의 수가 달라진다. 최소 곱셈 횟수를 찾는 것이 문제의 목표이다. 어떤 n이 주어졌을 때, A0A1...An-1에서 모든 곱셈의 경우를 보고 그 최소값을 찾아야된다. 곱셈의 결과를 저장하는 배열을 dp라고하고 dp[i][j]를 i부터 j번째까지의 최소 곱셈의 수를 저장한다. 행렬의 행과 열의 값을 페어로 저장하여, a에 저장한다. a[i].first는 Ai행렬의 행, a[i].second는 Ai행렬의 열의 값을 가진다. 이때 dp[i][i] = 0이고, 1 n; for (int i = 0; i > l >> r; a.push_back(make_pair(l, r)); dp[i][i] = 0; } for (int ..
Codeforces Round #641 (Div.2) A. Orac and Factors f(n)은 n을 나누는 가장 작은 소수를 출력한다. 에라스토테네스의 체를 사용하여, 10^6 까지의 n에 대하여 f(n)을 구한다. 코드에서는 minDiv배열에 해당값을 저장하였다. n = f(n) + n 을 k번 반복한다. test case의 수가 100개 k가 10^9 개 이므로 k번 반복해서는 time out이 발생한다. 두번째 계산부터 f(n)은 무조건 2인데, 이는 f(n) + n의 값이 무조건 짝수이기 때문이다. f(n)이 홀수 일경우 n도 홀수이고, f(n)이 짝수인경우는 n또한 짝수이다. 이를 통해 답을 계산하면, ans = f(n) + n + (k-1) * 2 가 된다. #include using namespace std; int minDiv[1000010]; int main(){ int..
Sudoku 풀어주는 프로그램 Sudoku Solver solve ... clear 사용자가 입력하면 입력부분이 회색으로 변하며 값이 고정됩니다. 값을 지워주면 고정값을 해제할 수 있습니다. 키보드 방향키를 이용해서 칸을 이동할 수 있습니다. Solve 버튼을 누르면, 사용자가 입력한 값을 기준으로 스도쿠를 풉니다
Codeforces Round #635 (Div. 2) C. Linova and Kingdom 문제 왕궁에는 n개의 도시가 있고, n-1개의 양방향 도로를 도시에 연결한다. 도시는 1번부터 n번까지 숫자가 붙여져있다. 1번 도시가 수도이며, 왕국은 트리 구조이다. 여왕은 정확히 k의 도시에 산업을 발전시키며 다른 도시들은 관광산업을 발전시킨다. 회의는 1년에 한번 수도에서 진행되는데, 각 산업 도시에서는 대표들을 수도로 보낸다. 대표들은 최단 경로를 따라서 수도에 이동한다. 관광도시를 여행하는 것은 즐겁고, 각 대표의 행복도는 수도에 이동하는 동안 방문한 관광도시의 개수이다. 여왕은 k의 산업도시를 잘 배치해 대표들의 행복도의 합을 최대로 하고 싶다. 풀이 산업도시가 수도와 얼마나 떨어져 있는지, 즉 depth 값이 각 산업도시의 행복도이다. DFS로 모든 노드를 방문하여, Depth의 내림차순으..
Codeforces #618 (Div. 2) B. Assigning to Classes 학생들을 두개의 class로 나누고, 두 class의 median 값의 차를 최대한 줄여야 한다. 배열 a가 정렬이 되어있다고 하면, 두 class의 중앙값은 a[n-1]과 a[n]이 되어야 그 차이가 최소가 된다. 만약 한 class의 중앙값이 a[n-2]으로 설정이 되었다면, 다른 클래스의 중앙 값은 아무리 작아도 a[n] 이 된다. #include #include using namespace std; int main(){ int t, n; cin >> t ; while (t-- ){ cin >> n; int a[200010]; for (int i = 0; i > a[i]; } sort(a, a+ 2*n); cout

티스토리툴바