곧죽어도 콛잉

https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 1) 빈칸 중 3개를 뽑는 경우를 모두 찾는다. 2) 각 경우마다 씨앗을 심는다. 그리고 꽃이 폈을때(즉, 상하좌우를 확인할때) 조건에 맞는지 확인한다. 3) 만약 확인한 경우가 잘못됐다면, 다른 경우로 넘어가고, 아니라면 총 비용을 계산해서 최소값인지 확인한다. 이 문제는 전형적인 완전 탐색 문제이다! 이 문제의 시간복잡도는 아무리 커도 20만을 넘기지 않는다. (100 combination ..

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 1) 0부터 9까지의 순열을 구한다. 2) 구한 순열의 모든 경우의 수를 부등호 사이에 넣어본다. 3) 2)에서 통과한 경우를, long으로 변환한 후 최소값인지 최대값인지 판별한다. 4) 모든 경우의수를 확인하면 최소값과 최대값을 출력한다. 진짜.. 쉬웠는데.. 헛짓거리를 많이했다... 문제 풀기전에 우리가 원하는 결과값의 데이터타입을 꼬오오오옥 확인하자 아무것도 모르고 atoi(s.c_str..

https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 1) 상하좌우로 dfs를 시행한다. (총 4번의 dfs) (참고로 x,y,x2,y2 input 모두 (1,1) ,,, (M,N)으로 들어오므로 -1 해줘야한다..) 2) 1번의 점프가 끝났으므로, res를 업데이트 3) 만약 dfs에서 #를 찾았다면(chk==1) res를 출력하고 종료. 4) 아직 #을 못찾았다면, 다시 dfs를 수행해야하므로 사용된 vis를 0으로 업데이트 해준다. ..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 1) 빈도수를 저장해야하므로 맵 자료구조를 사용한다. 이때, 맵 자료구조를 하나 더 사용하여 나온 순서도 저장한다. 2) 저장된 맵 자료구조를 정렬해야하므로 vector에 저장해준다. 3) 빈도수 정렬의 규칙에 따라 cmp 함수를 설정하고 sort를 진행한다. 4) vector를 출력한다. 우선 해당 수 : 빈도 수 가 필요하다는 것은 바로 알아차렸을 것이다. 그렇다면 바로 써줘야하는 자료구조는 바로 map이다!!! map을 이용하면 매우..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1) 재귀함수 q(x, y, n)를 설정한다. - 종료조건 : n==1 이 되면 x,y에 해당하는 숫자를 push_back 해준다. - 반복 : x, y부터 x+n,y+n까지 탐색을 시작한다. 만약 x,y에 해당하는 숫자와 다른 숫자가 나온다면, q를 호출하여 4번을 재귀적으로 돌린다. 추가로, 여는 괄호 '(' 를 push_back 해준다. 4번의 재귀가 끝난다면, 닫는 괄호 ')'..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 1) psum이라는 누적합 배열을 만든다. 2) 누적합 배열을 이용해 각 K일씩의 합을 구한다. 3) 동시에, max 함수로 최대값을 구한다. 문제를 읽으면 이해하는 건 어렵지 않다. 하지만 이걸 그냥 문제 나온 그대로 코딩하면 백퍼센트 오버플로우 혹은 타임 아웃이다.. 이 문제는 누적합을 이용하는 문제이다. psum[n]이라는 배열을 1일차부터 n일차까지의 합이라고 해보자, 그렇다면..