본문 바로가기

전체 글14

백준 19576번: 약수 https://www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net a < b < c 일 때, a, b가 배수 관계이고, b, c가 배수관계면 a, c가 배수 관계인점을 이용했다. 주어진 숫자들 사이의 배수관계를 찾아서 이어주고, 각 숫자마다 배수관계를 몇 번 이어나갈 수 있는지 최대값을 찾아서 전체 숫자 개수에서 빼주었다. 예제 입력을 예시로 들면 5 24 10 4 6 3 [3] - [6, 24] [4] - [24] [6] - [24] [10] - [] [24] - [] 위처럼 연결할 수 있고, 이때 3 - 6 - 24로 최대 3개가 연결될 수 있기 때문에 답은 5 - 3 = 2가 된.. 2022. 10. 6.
백준 1389번: 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 플로이드-워셜 알고리즘을 이용했다. 친구관계가 주어진 경우는 1로, 아니면 INF로 두고 i번 친구와 j번 친구가 몇 단계만에 이어질 수 있는 지 확인했다. i -> j로 갈 수 있다면 1, k번 친구를 거쳐야 한다면 d[i][k] + d[k][j]로 구할 수 있다. #include #define INF 10000 using namespace std.. 2022. 8. 9.
백준 5464번: 주차장 https://www.acmicpc.net/problem/5464 5464번: 주차장 시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영 www.acmicpc.net 하라는 대로 했다. k > 0 일 때, 1 ~ n 까지 주차장에 빈 칸이 있는 지 확인하고 비어있는 칸이 있다면 (k번 차의 무게 * 해당 칸의 요금)을 답에 더한다. 비어있는 칸이 없다면 대기열에 k를 추가한다. k < 0 일 때, k번 차를 뺀 후, 만약 대기열이 있다면 k번이 빠진 자리에 넣고 (대기열에 있던 차의 무게 * 해당 칸의 요금)을 답에 더한다. #include using namespac.. 2022. 8. 6.
백준 11502번: 세 개의 소수 문제 https://www.acmicpc.net/problem/11502 11502번: 세 개의 소수 문제 정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다. '5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 www.acmicpc.net 소수들을 모두 구하고 1000 이하의 수를 세 개의 소수 합으로 미리 구해놓고 출력했다. #include using namespace std; int t, K; bool arr[1000]; int ans[1000]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); for(int i=2 .. 2022. 8. 5.

티스토리툴바