🔗 문제 2467번: 용액 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net ✏️ 풀이 문제에서 보아야 할 것은 이미 용액이 "정렬된 상태 "인 것이다. 더 해야 할 용액도 2개다 싶어서 투포인터를 떠올렸다. 양 끝을 start, end라는 변수로 가리키며 그 합을 sum에 저장해 주었다. 이때 값은 오름차순 정렬이므로 start는 가장 작은 값(0 위치), end는 가장 큰 값 (N-1 위치)을 가리킨다. 만약 sum이 0이라면 더 이상 진행할 필요가 없다. 만약 sum < 0 이라면 작은 값을 가리키는..

🔗 문제 21609번: 상어 중학교 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 🖍 풀이 6달전에 푼거보다 개선되어서 다시 올리는 풀이 ✌🏻 문제를 읽고 코드 흐름을 간단하게 정리해보자. while(flag) { //1. 블럭 그룹들 찾기 //2. 조건에 맞는 블럭 제거하고 점수 얻기 // => 블럭 없으면 종료 flag = false //3. 아래로 중력 작용 //4. 반 시계 방향으로 회전 //4. 아래로 중력 작용 } 조건 정리 ✔️ 맵의 상태는 3가지의 블럭 종류와 빈 칸으로 이루어진다. enum..

🔗 문제 23290번: 마법사 상어와 복제 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net ✏️ 풀이 일단 이 문제는 내가 무려 밍기적 거리는 시간 포함해서 2주 동안 못 풀고 있던 것입니다. 이유는 예제 4, 5, 8에서 오답이 나와서, 다음은 예제 5번이 안 나와서. 총 2번의 대수정을 거쳐서 메모리 2028KB, 0ms로 문제로 맞았습니다!! 를 보게 됐다. 풀이 안 쓰려고 했는데 나한테도 도움될 것 같아서 오랜만에 자세히 써보고자 한다.. 문제를 읽으면 알겠지만, 간단하..

🔗 문제 11404번: 플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ✍️ 풀이 제목부터 거저주는 플로이드 기초 문제 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 플로이드 와샬이다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 그렇다면 A→B 중 가장 작은 비용 값을 저장하자. 💾 소스 #include #include #include const int INF = 1e9; std::vector adj; int N..

🔗 문제 1389번: 케빈 베이컨의 6단계 법칙 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net ✍️ 풀이 무방향 그래프에서 모든 정점의 최단 경로를 구해야 한다? 플로이드 와샬 문제였다. 주의 사항 무방향 그래프이므로 a→b면 b→a임을 잊지 말자. 플로이드 와샬이 방문하지 않은 인접행렬의 초기값은 INF이지만 이 문제에서 자기 자신으로 가는 값은 0으로 설정하는 것에 유의해야 한다. 출발노드가 중간노드나 목적지가 되는건 찾을 필요가 없다. 💾 소스 #incl..

🔗 문제 1956번: 운동 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net ✍️ 풀이 방향 그래프로 표현되는 경로에, 두 정점의 최단 거리를 구한다? 플루이드 와샬을 이용해서 푼다. 그래프가 주어졌을 때 두 정점의 최단 거리를 구할 때 사용한다. 그래프를 인접 행렬로 표현하며, 아직 경로를 찾지 못한 곳은 INF이다. 플루이드 와샬의 핵심은 a→b로 이동하고자 할때 중간 노드를 고려한다는 점이다. O(V^3)의 시간이 걸리지만 v가 400으로 작은 축에 속해서 문제를 풀 수 ..

🔗 문제 1949번: 우수 마을 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net ✍️풀이 문제를 읽어보면 트리 구조의 마을에 정점에 가중치가 주어진다. 마을은 인접한 마을끼리 우수마을이 될 수 없으며, 우수 마을이 아닌 곳은 적어도 하나의 우수 마을과 인접해야 한다. 어떤 노드를 선택했을 때, 그 마을을 우수 마을로 하느냐 하지 않느냐에 따라서 어떤 합이 나올지 몰라 계산이 필요한 식이다. 그냥 여기서 dp가 떠올랐다. 하지만 .. 어떻게 문제를 풀지는 감이 잡히지 않아서 인터넷의 도움을..

🔗 문제 1937번: 욕심쟁이 판다 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓..

🔗 문제 1676번: 팩토리얼 0의 개수 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🖍 풀이 아래 블로그를 읽고 이해한 문제 🔗https://sdev.tistory.com/808 [C/C++] 백준 #1676 팩토리얼 0의 개수(수학) 이번 문제는 팩토리얼을 계산했을 때, 뒤에서부터 연속된 0의 개수를 세는 것입니다. 팩토리얼은 1부터 n까지의 곱을 계산한 것인데요. 20 팩토리얼만 해도 2,432,902,008,176,640,000 값이 나와서 정수 sdev.tistory.com 문제 조건이 N ≤ 500으로 factorial(500)을 하면 엄청나게 긴 숫자에 시간초과가 뜰 수 있다. ..

🔗 문제 11403번: 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 🖍 풀이 DFS를 이용하여 풀었다. N개의 각 정점으로 부터 DFS를 이용해 연결된 모든 정점을 visited로 표시했다. 여기서 DFS에서 사이클을 무한반복하지 않도록 방문하지 않은 정점으로만 가는 조건을 반드시 걸어주어야 한다. 💾 소스 #include const int MAX = 100 + 1; bool graph[MAX]..