본문 바로가기

분류 전체보기

 (236)
C++[백준]20303번 할로윈의 양아치 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 솔루션 친구들을 하나의 묶음으로 묶고 냅색을 수행하면 된다. 1. bfs를 이용해 그룹의 인원과, 사탕의 총 개수를 구한다. 2. 냅색을 이용한다.. (오랜만에 글을 써서.. 그런가.. 엄청 짧다..) 코드 #include #include #include using namespace std; int N, M, K..
C++[백준]1915번 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 솔루션 dp 문제로, 가장 큰 정사각형을 만들 수 있는 한 변의 길이를 저장하면서 dp 테이블을 채워 나간다. 그리고 만들 수 있는 정사각형의 한 변의 길이를 구하는 점화식은 대각선 위, 위, 왼쪽 중 가장 작은 값에서 +1 을 해 주면 된다. 코드 #include using namespace std; int N, M; int arr[1002][1002]; int dp[1002][1002]; int main() { ios_base::sync_with_stdio(fal..
C++[백준]22342번 계산 로봇 https://www.acmicpc.net/problem/22342 22342번: 계산 로봇 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 www.acmicpc.net 솔루션 맞왜틀로 골머리를 앓았다. DP 문제인 건 알겠으나, r-1, c-1 r , c-1 r+1, c-1 중에서 최대 값을 저장 값으로 해 주었으나 어딜 틀렸는지 모르겠어 머리를 쥐어짜다 이리저리 수정하다 보니 성공했다. 일단 점화식이 다음과 같은 3가지 경우만 나눠지는 이유는 저장 값은 -1보다 더 이전 열에서 갖고 올 수 있지만 -1에서 더 이전의 열에서 가장 높은 저장 값을 가져와 저..
Deque 활용 문제 풀이 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 솔루션 deque를 이용해서 해결이 가능하다. 먼저 deque에 1~N까지 숫자를 차례대로 push_back을 해 준다. 그리고K-1만큼 deque.front()에서 뽑아주고, deque.push_back()을 해 준다. 이를 deque가 빌 때 까지 반복한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, K..
확장된 유클리드 알고리즘 문제 세 양의 정수 a,b,c가 입력으로 들어온다. 이 때, ax +by = c를 만족하는 정수 x,y를 찾되, |x| + |y|가 최소가 되는 x,y를 찾아라. 입력 첫째 줄에는 테스트 횟수를 나타내는 T가 들어온다. 다음 줄 부터 한 줄에 세 정수 a,b,c (0 < a,b,c, < 10^8 -1)가 순서대로 주어진다. 출력 |x| + |y|가 최소가 되는 일반해를 출력하라. 찾을 수 없다면 -1을 출력하라. 솔루션 아직 확장된 유클리드 알고리즘에 대해서 이해가 깊지 않지만, 먼저 각각의 입력을 받고, 서로소로 만들어준다. 확장된 유클리드 알고리즘으로 s1,t1을 구한다. 그리고 구해진 gcd로 c를 나눴을 때, 나머지가 있다면, 해가 존재하지 않는다. 나눠진다면, 그 몫을 s1,t1에 곱해준다. (..
C++[백준]14846번 직사각형과 쿼리 https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net 솔루션 특정 인덱스(x,y)에서 1~10의 수를 몇개씩 갖고있는지 저장해둔다. 나는 구조체 내부에 배열을 선언하여, 1~10까지 몇 번 등장했는지, 저장해둔다. 특정 인덱스에서의 등장횟수를 찾는 법은 1. 현재 인덱스에 배열의 값을 ++ 2. [x-1][y]에서의 등장 횟수 + [x][y-1]에서의 등장 횟수 - [x-1][y-1]에서의 등장횟수를 해 주면 특정 인덱스에서의 총..
C++[백준]1658번 돼지 잡기 https://www.acmicpc.net/problem/1658 1658번: 돼지 잡기 첫째 줄에 돼지 우리 숫자를 나타내는 M(1≤M≤1,000)과 손님들의 숫자를 나타내는 N(1≤N≤100)이 공백으로 구분되어 주어진다. 돼지우리는 1번부터 M번까지의 숫자로 매겨져 있고 손님 역시 1번부 www.acmicpc.net 문제가 좀 조건대로 하면... 안풀리는 것인데 풀리니 이상하다 생각을 하고 푼 문제. (솔루션을 봤음..) 처음에 조건 3.을 제대로 보지 않아서 소스 - 돼지우리 - 사람 - 싱크 이렇게 노드를 연결하여 풀 수 있을 것이라 생각했다. 그런데 문을 열었을 때, 남은 돼지를 적절히 재분배 할 수 있다는 조건이 상당히 까다로워졌다. 도저히 문제를 해결못해서 솔루션을 봤다. 원래라면 디닉으로..
C++[백준]1996번 지뢰 찾기 https://www.acmicpc.net/problem/1996 1996번: 지뢰 찾기 첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 지뢰 찾기 map에 대한 정보가 주어지는데 '.' 또는 숫자로 이루어진 문자열이 들어온다. '.'는 지뢰가 없는 것이고 숫자는 지뢰가 있는 경 www.acmicpc.net 솔루션 입력으로 들어오는 문자열을 따로 저장해 두고, 2중 for문을 돌면서 8방위에 '.'이 아닌 것이 있다면 무조건 숫자이기 때문에, 숫자로 변환해주어 더해준다. 8방위로 탐색을 할 때는 int dx[8] = { 1,0,-1,0,1,-1,1,-1 }; int dy[8] = { 0,1,0,-1,1,-1,-1,1 }; 각각의 방향을 배열에 저장해 두고 for문을 돌면 더욱 간..

티스토리툴바