문제 풀이
-
[SWEA] 2112. 보호필름문제 풀이 2020. 5. 4. 18:27
2212 보호필름 풀이)재귀 + 브루트 포스 문제였다. 필름 막 상태를 vector arr;에 저장해 놓았다.그리고 약품으로 막 상태를 바꾼다면 기존의 값을 알아놔야하기 때문에 처음에는vector temp =arr; 로 전체 상태를 저장해놓은 뒤,막 상태 바꾼 후 arr= temp; 로 돌려놓았는데 이렇게 하니 시간초과가 났다. 아무래도 백터 전체를 저장하고 돌려놓고 해서 그런듯 싶어 두번째로는 필름 막 상태 모두를 저장해놓지 않고,기존의 막 상태(행)만 저장해두고 vector temp = arr[i]; (i는 바꿀 막 인덱스)상태 바꾼 후 원래 막 상태로 바꿔주도록 했더니 arr[i] = temp;시간 초과가 나지 않고 통과했다. 시간초과가 나지 않게 사용한 방법은 위에서 설명한 거 말고 2가지가 더있..
-
[SWEA]2105 디저트 까페문제 풀이 2020. 5. 1. 21:42
2105 디저트 까페 풀이)dfs를 이용해서 푼 문제이다. 최대한 중복되는 사각형 모양을 거르기 위해 두가지 방법을 사용했다.1. 맨왼쪽, 맨오른쪽, 맨아래쪽에서 시작하는 경우는 사각형을 이루지 못하므로 계산에서 제외한다.2. 사각형으로 움직일때, 무조건 오른쪽 아래부터 시작한다. 주의할 점출발점으로 돌아왔을때, 디저트의 수는 무조건 4개 이상이며 방향으로 제일 마지막 방향 상태여야한다. 코드) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include using namespace std; int n;int map[21]..
-
[SWEA] 1949 등산로 조성문제 풀이 2020. 4. 29. 22:24
1949 등산로 조성 풀이)dfs를 이용해서 가능한 모든 경우를 다 살펴본 문제이다. 과정은 이러하다.1. 가장 지형이 높은 곳들의 위치를 저장해 둔다.2. 각 높은 곳들의 위치에서 dfs를 통해 등산로 길이를 구한다.3. 그 중 최고의 등산로 길이를 출력한다. dfs함수를 자세히 설명하면1) 현재 좌표값에서 상하좌우로 움직였을때 지도 범위내에 들어오는 지 확인2) 범위내에 들어온다면 이전에 지형을 깎아본 적이 있는 지 확인 2.1) 지형을 이미 깎아봤다면다음에 움직일 곳의 지형의 높이 확인현재 지형의 높이보다 작다면 → 이동작지 않다면 →이동 그만하고 지금까지의 등산로 길이 체크 2.2) 지형을 아직 깎아보지 않았다면다음에 움직일 곳의 지형의 높이를 확인현재 지형의 높이보다 작다면 → 이동작지 않다면 ..
-
[SWEA] 2817 부분수열의 합문제 풀이 2020. 4. 28. 22:14
2817 부분수열의 합 풀이)3752 가능한 시험 문제 와 비슷하게 풀면 된다. 코드) 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std; int arr[20];int dp[100000]; int main() { //freopen("sample_input.txt", "r", stdin); int T = 0; scanf("%d", &T); for (int test_case = 1; test_case
-
[SWEA] 1928 Base Decoder문제 풀이 2020. 4. 27. 20:01
1928 Base Decoder 풀이) Encoding 과정이1. 3byte, 24bit 문자를 집어넣는다2. 6bit씩 잘라서 아래 표로 encoding한다. (2^6 = 64 개 문자 표현가능) 이니깐 반대로 decoding하려면1. 문자를 6bit 이진수로 바꾼다.2. 24bit가 모였으면, 8bit씩 잘라서 3개의 문자를 만든다. 주의encoding 한 문자의 값은 아스키 코드의 값과 달라서 변경해줘야한다. 아스키 코드 값. 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include #include #incl..
-
[백준] 17244번 아맞다우산문제 풀이 2020. 4. 26. 21:44
17244 아맞다우산 문제경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다."아 맞다 우산!!!"경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.경재 씨를 위해 집을 위에..
-
[SWEA] 2805 농작물 수확하기문제 풀이 2020. 4. 23. 22:32
2805 농작물 수확하기 풀이) 농작물의 가치를 배열에 저장한 뒤,중간에 있는 행의 값부터 위아래 각자 행의 값까지 for문을 돌면서 더했다. 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041#include using namespace std; int arr[50][50]; int main() { //freopen("input.txt", "r", stdin); int T = 0; scanf("%d", &T); for (int test_case = 1; test_case
-
[SWEA] 2806 N-Queen문제 풀이 2020. 4. 23. 00:13
2806 N-Queen 풀이) 완전 탐색 문제이고,퀸이 같은 행, 열 또는 대각선에 놓일 수 없다는 점을 잘 생각해서 풀면 되는 문제이다. 퀸은 같은 행에 놓일 수 없다 ↓ 한 행 당 하나의 퀸만 놓일 수 있다. 를 기준으로 각 행 당 어떤 열에 퀸을 놓을 때, 이전 행들이 퀸을 놓은 열과 직선인지 혹은이전 행들이 퀸을 놓은 열과 대각선인지 를 확인해서 두 경우에 해당하지 않는 경우에만 퀸을 놓아줬다. (이전 행들이 퀸을 놓은 열들은 1차원 배열을 통해 저장해줬다.int row[10] // row[i] = j -> i번째 row j번째 column에 퀸이 놓여졌다.) 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041..