[백준 / C++] 1620번: 나는야 포켓몬 마스터 이다솜

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net C++에 구현된 unordered_map STL을 이용하면 쉽다. 포켓몬 번호를 입력받고 포켓몬 이름을 출력해야 할 때는 unordered_map에서 index로 가져오는 것보다 배열에 따로 저장해 거기에 있는 index로 바로 출력하는 게 더 빨라서 name이라는 배열을 따로 만들었다. #include using namespace std; unordered_map P..

• format_list_bulleted PS/백준
• · 2023. 7. 16.
• textsms

[백준 / C++] 2630번: 색종이 만들기 (재귀, 분할 정복)

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 재귀, 분할 정복 (Devide and Conquer) 구현 방법 색종이의 맨 왼쪽 위 index부터 시작해 색종이의 크기만큼 arr[i][j]를 탐색하다가 맨 왼쪽 위 원소와 다르면 색종이를 4등분 한다. 잘려진 색종이의 한 변의 길이는 현재 색종이 한 변의 길이의 절반이다. 4등분할 때 잘려진 각 색종이의 왼쪽 위 좌..

• format_list_bulleted PS/백준
• · 2023. 7. 15.
• textsms

[백준 / C++] 17615번: 볼 모으기 (그리디 알고리즘)

https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 난이도: solved.ac 실버 1 접근 방법 결론: R과 B를 각각 맨 앞으로 옮기는 경우, 맨 뒤로 옮기는 경우 이렇게 총 4가지 경우의 수를 구해야 한다. 아래의 경우를 보자. RRRBBBRRBBRBRR R의 총 개수는 8개이고 맨 앞에 R이 3개 연속으로 있고 맨 뒤에는 R이 2개 연속으로 있다. R을 모두 맨 앞으로 몰아넣으려면 뒤에 있는 5개(전체 R의 개수..

• format_list_bulleted PS/백준
• · 2023. 7. 15.
• textsms

[백준 / C++] 6064번: 카잉 달력

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 난이도: solved.ac 실버 1 중국인의 나머지 정리? 를 이용해서 푸는 거라던데, 유클리드 호제법도 잘 모르는 나는 그냥 내 식대로 풀어봤다. 를 만들기 위해 먼저 부터 시작해서 두 번째 자리에 있는 x를 y로 만드는 것을 목표로 했다. 예를 들어 예제 입력 1의 첫 번째 케이스처럼 m = 10, n = 12, x = 3, y = 9라면, 일단 부터 시작해서 앞자리가 3인 다음 경우를 생각해 보..

• format_list_bulleted PS/백준
• · 2023. 7. 13.
• textsms

[백준 / C++] 1956번: 운동 (플로이드 워셜 알고리즘)

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 이론, 플로이드 워셜 (Floyd-Warshall) 접근 방법 다익스트라 알고리즘을 이용할 수도 있겠지만 정점의 개수가 적으므로 플로이드 워셜 알고리즘을 이용하였다. 구현 기존의 플로이드 워셜 문제에서는 자기 자신으로 가는 비용은 0으로 초기화했지만, 이 문제에서는 자기 자신을 포함한 모든 노드로 가는 비용..

• format_list_bulleted PS/백준
• · 2023. 7. 13.
• textsms

[백준 / C++] 11404번: 플로이드 (플로이드 와샬 알고리즘 - Floyd Warshall Algorithm)

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 이론, 플로이드 워셜(Floyd-Warshall) 접근 방법 플로이드 워셜 (플로이드 와샬) 알고리즘을 그대로 구현하면 되는 문제다 자기 자신으로의 가는 비용은 0으로 두고, 자기 자신을 제외한 나머지 모든 노드로 가는 비용은 INF(가장 큰 수)로 둔다 그리고 점화식을 이용해 다른 노드로 가는데 드는 최소 비용을 계산한다 코드 #inclu..

• format_list_bulleted PS/백준
• · 2023. 7. 13.
• textsms