www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 배열하나 잡고 dfs돌리면서 방문처리 해주면 되는 쉬운 문제인줄 알았으나 5연속 연타임 에러를 맞고 다시 꼼꼼히 살펴봤다. 일단 배열의 크기는 아무리 커도 9^5 * 5 이니 30만을 넘지 않는다. #include #include using namespace std; int vis[300000]; int a, p, ans; int cal(int n) { int ret = 0; while (n > 0) { ret += (int)pow(n % 10, p); n /= 10; } return ret; } void dfs(int ..

www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제를 이해하는 것은 어렵지 않다. 인덱스를 돌면서 방문처리 해주는 간단한 문제였는데, 그래프의 탐색중 기초문제같다. #include using namespace std; int ar[1001], tc, n, cnt; bool vis[1001]; void dfs(int cur) { if (vis[cur]) return; vis[cur] =..

˙www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디하게 접근하면 쉽게 풀리는 문제다. 내 접근법은 이렇다. 1. 현재 지역이 다음 지역보다 가격이 비싸다면 그 다음 지역을 검색해서 현재 지역보다 싼 지역을 찾음 2. 현재 지역보다 싼 지역을 찾았다면 그 지역까지의 거리값만큼 충전 후 이동 3. 이후 반복 단, 첫 번째 지역에서 반드시 충전해야 한다. #include using namespace std; using ll = long long..

www.acmicpc.net/problem/29812981번: 검문트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간��www.acmicpc.netar 배열에 입력받은 수들을 정렬해주고어떤 수 ar[i] = 몫*나눈값+나머지 이므로 나머지를 처리해줘야 하니ar[i] - ar[i-1] = 나눈값(몫-몫2) + (나머지-나머지) 이다나눌 값들은 각각에 배열들에 대해 최대공약수를 구해서 그 최대공약수의 약수들로 나눠주면 같은 나머지가 출력된다. #include #include #include using namespace std; int GCD(int x, int y) { if (..

백준 문제를 풀던 중 약수에 대해 공부할 기회가 생겨 찾아보던 중에 에라토스테네스의 채와 같이 제곱근의 형태를 띄는 최적화를 알게 되었다. for (int i = 1; i

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이번에 풀어본 문제는 대표적이라 하는(?) 냅색 문제이다. 냅색 문제는 가방에 무게와 가치가 주어졌을 때, 가방의 무게 안에 가장 큰 가치를 챙기게 하는 로직으로 가야한다. 그리디한 방식으로는 전부 반례가 있다. #include using namespace std; int n, k, ar[101][2], d[101][100001]; int mai..