https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 1. Logic 1. 인접한 두 칸에 있는 사탕을 서로 바꿔야하기 때문에 swap함수를 사용해서 값을 변경해 준다. 2. 같은 색의 사탕을 먹어야 하기 때문에 현재칸과 그 다음칸을 비교하면서 진행하며 cnt를 올려준다. 3. 최댓값을 갱신해준다. 2. Code #include using namespace std; vector vec; int n; int calc() { // 가로 int ans = -92735; for(int i = 0; i < n; i++) { int cnt = 1; for(int j = 0; j..
전체 글
https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1. Logic 2가지 상황으로 분할해 볼 수 있다. 1. n이 99이하인 경우 2. n이 100이상인 경우 - 1 ~ 99까지의 수는 항상 등차수열을 이루기 때문에 99이하의 숫자가 나오게되면 즉시 숫자를 리턴한다! - 100이상의 숫자는 어짜피 999까지 비교하면 되기 때문에 3부분으로 나눠서 100자리 10자리 1자리 숫자를 각각 비교한다. 2. Code #include using namespa..
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 1. Logic - 받은 숫자를 오름차순으로 정렬한다. 처음 숫자부터 더해가며 sum > vec[i] 일 경우 수를 조합하여 구할 수 있고 sum > n; for..
https://www.acmicpc.net/problem/10448] 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 1. Logic - 세 합이 100을 넘는 경우는 n이 45인경우부터 1000을 넘기 때문에 45까지 for문을 돌며 합을 계산해 놓는다. - 계산하고 싶은 삼각수를 받은 후 3중 for문을 돌며 찾게되면 값을 반환한다 2. Code #include using namespace std; int triangleNum[1001]; bool FindTri(int n) { for(int i =..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 1. Logic 1. 난쟁이들의 키의 총 합이 100이고 난쟁이들의 수가 정해져있기 때문에 키를 입력받으면서 동시에 전부 더해준다 2. 2명을 제외하면 되기 때문에 2중 for문을 돌면서 2명의 키를 뺀것이 100이 되면 출력해준다. 2. Code #include using namespace std; vector vec; int main() { int sum = 0; for(int i = 0; i < 9;..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. Logic - 딱 봐도 BFS지만 나눠야 하는 부분이 3가지이다. 1. 조건을 같지 않을때로 걸고 BFS를 돈다 2. 이후 배열을 순회하며 R 또는 G중 원하는 것을 선택하여 R > G / G > R로 변경해준다. 3. 다시 BFS를 돈다. 2. Code #include using namespace std; int n; vector vec(101, ""); vector vis(101,..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. Logic - 기본 다익스트라 문제이다. 문제에서 나온대로 한 정점에서 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘을 사용하면 풀 수 있다. 다 돌고 배열에서 값만 하나씩 출력해주면 되는 문제 2. Code #include using namespace std; const int INF = 10000000; // 시작 노드에서 해당 노드까지의 경..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. Logic - 다익스트라는 한 정점에서 모든 정점으로 가는 최단경로를 구하는 알고리즘이다. 이 문제는 한 정점에서 모든 정점으로 가는 최단거리 + 다시 집에가는 최단거리 두개를 구해서 더해야 한다 2. Code #include using namespace std; const int INF = 987654321; //최소 비용 배열 int d[1001]; vect..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. Logic > 기본 DFS / BFS문제 Depth First Search(DFS) - 재귀를 사용하며 자기 자신을 호출하여 깊게 들어가며 노드를 확인하며 검색한다. - DFS를 구현할 때 주의해야할 점은 탐색한 경우 방문처리를 하여 다시 들어가지 않도록 하여 무한루프에 빠지는 것을 필히 방지하여야 한다. 기저조건을 잘 파악하고 방문처리를 해야한다. Br..
https://www.acmicpc.net/problem/2785 2785번: 체인 희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그 www.acmicpc.net 1. Logic - 부분 문제로 나눠서 생각을 해봤을 때 1. 원래 있는 체인을 사용해서 연결하는 경우 2. 서로 끝부분끼리 연결하는 경우 이렇게 두가지로 나누어진다고 생각했다. 원래 있는 체인을 사용하는 경우 연결하는 부분의 갯수가 체인의 길이를 넘게 되면 항상 비효율적으로 사용하기 때문에 사용하는 기존 체일을 제외한 갯수와 사용하는 체인의 갯수가 똑같아야만 한다. 서로 끝부분끼리 연결하는 경우 갯수..