2020.02.14 큐빙 풀이 알고리즘 : Simulation box[6] 에 큐브의 6개 면에 대해 char 를 인덱싱 할 수 있도록 써두었다. color[6]에 큐브 6개의 면을 초기화 할 색깔들을 써두었다. myCube에 6개의 면(각 면마다 3x3) 의 색들을 담았다. turnIdx 배열을 통해 6개의 면 중 바라보고 돌릴 면과 이때 바라보는 면을 둘러싸는 4개의 면을 아래,오른쪽,위,왼쪽 순으로 찾을 수 있도록 써두었다. turnInfo : 6개의 면 중 바라보고 돌릴 면을 정했을 때 turnIdx에서 나온 결과에 따라 해당 index들 중 기준점이 되는 점이 각 경우마다 달라지므로 경우에 맞게 써두었다. blockIdx : turnInfo에서 받아온 기준점에 따라 다음 두개의 숫자를 가져오는 ..

2020.02.12 나무재테크 Solution InMap : 매 턴 마다 양분의 값을 저장하는 변수 (초기값은 모두 5) deadMap : 봄에 죽은 나무들이 여름에 더해질 양분을 저장하는 변수 plusMap : 처음에 input으로 주어지는 로봇이 겨울에 더하는 양분 treeInfo : 칸에 있는 나무들이 저장되는 vector 변수 알고리즘 : Simulation 주어지는 정보에 맞게 spring, summer, fall, winter 함수를 만들어 K번 만큼 수행하고 살아있는 나무의 개수를 세어 출력. //! 2020.02.12 // TODO BJ16235_나무재테크 #include #include #include using namespace std; const int MAX = 15; const i..

2020.02.12 백준 12100 / 2048(Easy) Solution inMap : input map nextMap : 2048 게임이 진행됨에 따라 변경되는 map dirInfo : 완전탐색으로 1번째~5번째에 블락을 이동시키는 방향을 결정해둔 배열 myQ : 코드 1의 방식에서 사용될 Q check : 코드 2의 방식에서 사용될 bool 배열 알고리즘 기본적으로 5번의 턴에 사용될 방향을 완전탐색을 이용해 경우의 수를 구한다. O(4^5) 각 경우의 수 마다 5번의 턴을 수행시키고 최댓값을 갖는 블락의 수를 출력한다. 턴을 수행하는 방식은 기본적으로 방향에 따라 행/열 마다 블락들을 이동시키도록 구상하였다. 각 행/열 에서 블락들을 이동시키는 방식을 두 가지로 구현해보았다. Solution1 옮..

BJ17142 연구소3 2020.02.11 https://www.acmicpc.net/problem/17142 Solution inMap : input NxN map checkMap : BFS를 위한 bool map numBlank : 총 빈칸 갯수 myV : 바이러스 후보 좌표들 myQ : BFS를 위한 큐 vInfo : 완전탐색을 통해 얻은 0~M 까지의 활성화시킬 바이러스 index 정보 알고리즘 getResult 함수를 통해 완전탐색하여 0번 ~ myV.size()-1번 까지의 바이러스 중 M개를 고른다. (조합) 조합을 다 골랐다면(기저조건) BFS를 호출하여 탐색에 걸린 시간을 받아온다. 탐색했는데 빈칸이 존재한다면 INF를 리턴하여 실패했음을 알린다. 매 재귀호출에서 받아온 결과들 중 가장 ..

2020.02.10 구슬탈출2 Solution Input 자료 저장 : pair로 R,B 구슬의 위치를 저장한다. 기울임 dir을 순서대로 저장하는 dirInfo 배열 알고리즘 기본적으로 기울임 dir을 저장하는 배열에 완전탐색을 이용해서 경우의 수를 모두 저장한다. 저장이 끝날 때 dirInfo 배열에 있는 방향으로 1~10 까지 기울이면서 구슬을 움직인다. 이때 기울임의 방향에 따라 R,B 구슬 중 어느것이 먼저 움직여야 하는지 결정한다. (예를 들어 오른쪽으로 움직이도록 기울이는 경우 더 오른쪽에 있는 구슬을 먼저 움직인다.즉, x좌표가 더 큰 구슬을 먼저 움직인다.) 구멍에 빠지거나 벽을 만날 때 까지 움직인다. 이렇게 하게 되면 동시에 한 점에 놓일 일이 없고 만약 이 때 B 구슬이 구멍에 빠지..

2020.02.10 감시 Solution Input 자료 저장 : inMap을 양쪽으로 2칸씩 여유있게 선언해놓고 4방향을 6(벽)으로 덮어서 만들고 시작했다. 알고리즘 : 기본적으로 CCTV의 기준 방향을 완전탐색을 이용해 정하고 방향이 모두 정해졌을 때의 사각지대의 크기를 모두 비교하여 최소 크기를 리턴하는 방식 getResult 함수 : idx번째부터 끝까지 CCTV의 basis direction을 선택하는 재귀구조의 완전탐색 함수 getSize 함수 : 방향을 모두 선택한 getResult 함수의 기저조건에서 detectMap에 CCTV탐색을 각 방향과 CCTV의 종류에 따라 탐색하도록 만들었고 탐색이 완료된 후에 사각지대의 크기를 구하고 다시 detectMap을 초기화하여 사각지대의 크기를 re..

BJ17837 새로운게임2 2020.02.09 https://www.acmicpc.net/problem/17837 Solution 2차원 vector horseInfo를 이용해서 해당 칸에 있는 말들의 번호와 방향을 pair로 순서대로 담았다. 1차원 vector horse를 이용해서 k번말의 위치(r,c)를 pair로 담았다. getResult 함수 : 1000 번 돌리면서 말을 움직였을 때 4개 이상 올라가는 경우가 생기면 그때의 t를 return 해서 결과를 얻고 만약 1000번동안 없으면 -1을 리턴하는 함수. 1번 돌릴 때 1번말 ~ K번말까지 돌린다. Move 함수 : horse의 idx k 를 받아서 이동시키고 이동한 곳의 말의 수를 리턴하는 함수 1시간 반정도 소요되었는데, 문제를 잘못읽었..

BJ11401 이항계수3 2020.02.09 자연수 N에서 K를 뽑는 경우의 수 % 1000000007 Solution1 N 팩토리얼 / (K 팩토리얼*(N-K)팩토리얼) 이렇게 나눠주는 경우는 분자,분모를 구하는 과정에서 팩토리얼 곱셈 도중 나머지를 계산하는 방식을 사용할 수가 없다. 즉, 분자와 분모가 long long의 범위를 넘어가게 된다. Solution2> nCr = n-1Cr-1 + n-1Cr 임을 이용한다. 이렇게 하면 합으로 문제가 바뀌기 때문에 합을 1000000007로 매번 나누어 줄 수 있다. (즉, 범위를 넘기지 않을 수 있다.) 그렇지만 이렇게 하면 호출의 횟수가 급격히 늘어나게 된다. (마치 피보나치 수열처럼) N의 범위가 4000000 이하이므로 시간초과가 난다. DP를 사용..