[백준] 2661번 : 좋은수열 (C++)
https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 문제 : 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다. 처음에는 특정한 규칙이 있을 것같았지만, 손으로 몇개 나열해보니 규칙을 찾기가 어려웠다. 따라서, 백트래킹을 통해 작은 수부터 모든 경우의 수를 탐색하면서 좋은수열이면 즉시 종료하였다. 여기서, 중요한건 좋은수열인지 체크하..
2021. 9. 26.
[백준] 2003번 : 수들의 합 2 (C++)
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 연속된 숫자들의 부분합이 M이 되는 경우를 구하는 문제이다. for문으로 무작정 구현하면 시간초과가 나기 때문에, 두 포인터를 사용해서 효율성을 고려해야 하는 문제였다. (만약 주어진 숫자들이 자연수가 아니라면 두 포인터를 사용할 수 없다.) Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘으로, 최악의 경우..
2021. 9. 22.
