USACO(3) https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 판의 크기가 작고, 탐색 깊이가 깊지 않아서 브루트포싱으로도 충분히 문제를 해결할 수 있다. 4방향^6회 * 25가지 좌표 대략 10만번쯤 탐색할거같다. 6번 탐색하기 때문에 6번을 탐색해 만들어진 가장 큰 숫자는 999999 이므로, int범위도 벗어나지 않고, 문자열으로 붙여서 관리하는게 아니라 그냥 int로 관리해도 문제가 없다. 나..
USACO(2) https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net dfs나 bfs를 사용해서 물통을 옮기는 모든 경우를 브루트포싱해주면 된다. 용량이 A고 a만큼 차있는 물통에서 (B,b) 물통으로 물을 옮기고자 할때, 1) A물통을 다 비울수 있는 경우 >> (0,a+b) 2) A물통을 다 비울수 없는 경우 >> (a+b-A, B) 이렇게 물을 옮길수 있는 경우의 수는 3P2 = 6이니까 6가지 모든 경우에 대해서 계산해주도..
USACO 문제 푸는중 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net flood-fill 문제에 해당한다 인접한 구역끼리 묶어서 가장 큰 크기의 구역을 찾는 문제. 플러드필 같은경우는 dfs로 구현해도 되고 bfs로 구현해도 되는데, 취향껏 구현하면 된다. 나는 bfs를 사용해서 구현해 보았다. 입력으로 배열이 주어지는게 아니라, 좌표값만 주어지니까 주어지는 좌표값을 이용해서 2차원 배열을 직접 만들어..
@WillKiss님의 추천으로 USACO를 천천히 밀어볼까 싶다. https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 예시로 나온 테스트케이스 a, t, c, i, s, w의 경우, i번 문자열을 선택하거나 / 선택하지 않거나 의 두가지 선택지로 나눠 브루트포싱을 진행하면 전체 경우의 수는 2^6이 된다 C=2 && c_mo >=1) return true; else return false; } void dfs(string s, int idx){ if(i..
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 문제인데 아니 이걸 왜이렇게 오래 뇌절을 쳤는지 모르겠다 엉엉엉 시작점 S에서 이동하는 서커스 예술가가 갈 목적지 후보 중에서 G-H간 도로를 건너 이동해야 하는 경로를 구하는 문제. 즉, 목적지 후보를 K라 할때, S-K 로 이동하는 최단경로가 S-G-H-K 이거나 S-H-G-K 이면 가능한 경우에 해당하고, S-K로 이동하는 최단경로의 길이가 S-G-H-K 이거나 S-H-G-K..
https://www.acmicpc.net/problem/16900 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net fail 배열이 가지고 있는 값이 접두사와 접미사가 같아지는 최대 길이임을 이용하는 문제. 문자열 두개를 최대한 많이 겹쳐내면 전체 문자열의 길이가 가장 짧아지게 되기 때문에 가장 적극적으로 겹쳐내기 위해서 실패함수 값이 담긴 배열을 구해준다 가장 적극적으로 겹쳤을 때 전체 문자열의 길이는 (전혀 겹치지 않았을때의 최대 길이) - (겹쳐진 부분만큼의 길이) 이고 겹치지 않았을때의 최대 길이는 S.length() * K 로 ..