댄코 - 댄싱코딩

문제보기두단계로 나눠서 풀이했다.1.dfs로 사람들이 1번 계단으로 갈지 2번 계단으로 갈지 결정하는 모든 경우의 수를 도출2. 도출된 경우의 수로 cur변수를 1씩 증가시키며 계단에 도착하는지 검사-계단에 도착시 계단 높이 + 1을 계단 벡터(stairPool)에 push (계단에 도착 후 1분뒤 내려가기 시작하므로)-계단에 사람이 있다면 한칸씩 내려감-모든 사람이 내려갈때까지 반복 처음에 50개의 테스트 케이스 중 49개의 테스트 케이스만 맞아서 답답했다. 아마도 계단에 내려가는 사람이 3명으로 꽉 차서 대기하는 사람이 있을 때,어떤 사람이 계단 내려가기를 완료한 시점에서 대기하던 사람이 바로 내려갈 수 있어야하는데 그부분을 처리하지 못해서 그런것같다. #include #include #include..

문제보기1.10진수를 4비트 2진수로 변경 2.BFS로 뚫려있는 부분만 큐에 넣어 방 도출해서 각 방에 번호 붙임 => 방의 갯수, 가장 넓은 방 넓이 3.0,0부터 오른쪽 아래까지 현재 좌표에서 오른쪽, 아래쪽을 검사 하면서 방번호가 다르면 두 방의 넓이를 더한것 중 가장 큰것=>하나의 벽을 제거해서 얻을 수 있는 가장 넓은 방의 크기 #include #include using namespace std;int dy[4] ={1,0,-1,0};int dx[4] ={0,1,0,-1};int map[51][51]={0};int check[51][51]={0};int N,M;int checkNum = 1;int* getBinary(int n){ static int tp[4]; for(int i = 0;i

문제보기일반적으로 빙산문제와 같지만 배열의 크기가 1500*1500이기 때문에 다른 솔루션이 필요하다. 우선 전처리로 각 빙산이 몇일이 지나면 녹게 되는지 water배열에 저장하고 이를 이용한다.waterBFS에서는 이 water배열을 만들면서 모든 빙산이 녹은 날짜를 리턴한다.BFS에서는 백조 두마리가 만날 수 있는지 검사한다. main에서는 0부터 모든 빙산이 녹은 날짜 사이에 백조가 만날 수 있는 가장 최소의 날짜를 이분탐색으로 구해 답을 도출한다. #include #include using namespace std;int N,M;int map[1501][1501];int numMelt = 0;int numVisit = 1;int check[1501][1501]={};int water[1501][1..

문제보기 맥북 충전기를 두고와서 윈도우인 집 컴퓨터에서 웹 IDE를 사용해서 풀다보니 디버깅이 어려워서엉뚱하게 입력부분에서 헤멨던 문제.BFS를 사용해서 구간별로 늑대와 양의 수를 구한 후 양이 많으면 양의 수를 리턴,늑대가 많으면 늑대 수 * -1을 해준다. 메인에서 각각 양의수와 늑대 수 (*-1)로 답을 도출한다. #include using namespace std;char map[251][251]={};int check[251][251]={};int dy[4] = {1,0,-1,0};int dx[4] = {0,1,0,-1};int N,M;int BFS(pair n){ queue q; q.push(n); int wolf=0; int sheep=0; while(!q.empty()){ int y = q..

문제보기처음에 x,y를 y,x로 바꿔보겠다고 하다가 좌표가 엉켜서 여러번 틀렸었다. 좌표가 위아래가 바뀌어있어서 상하반전으로 생각하고 풀었다. 그 후 벡터에 첫좌표, 끝좌표, 아이템들의 좌표를 넣고 정렬해준 후 ,각 좌표 사이에 갈 수 있는 경로의 수를 DP로 구해서 전부 곱해주면된다. #include #include #include using namespace std;int map[101][101] = {}; int getLoadNum(pair n, pair m){ int dp[101][101]; int x1 = n.first; int y1 = n.second; int x2 = m.first; int y2 = m.second; //printf("position:%d %d %d %d\n",y1,x1,y2..

문제보기이분탐색으로 left = 0, right = 2^31 -1 로 시작해서 최적의 mid값을 구하는 문제다. 이때 mid값을 k개의 랜선길이로 나눠서 더한값(cnt)이 N 보다 클 때 result 에 mid값을 넣어줘야하는데 cnt갯수는 같지만 최대 길이가 아닐 수 있기 때문에 max함수를 이용한다. #include #include #include #include using namespace std; int main(){ int k,N; scanf("%d%d",&k,&N); vector a(k); long long l = 0, r = pow(2,31)-1, m =0; for(int i = 0;i

문제보기이분 탐색으로 left = 1, right = k를 시작으로 mid를 구하고 그 mid보다 작거나 같은 수의 갯수를 cnt에 저장한다. cnt를 구하는 이유는 k번째 수를 구하기 위해서 k보다 작은 수의 갯수를 구할 필요가 있기 때문이다. cnt(mid보다 작거나 같은 수)는 min( mid / i, N) --- (i 는 1부터 N까지)를 전부 더한값이다. 그 이유는 a[i][j]에서 i행은 i의 배수들로 이루어져 있기 때문.그때, i의 배수들이 N개를 넘을 수 없으므로 min함수를 이용한다. 그렇게 나온 cnt값(mid보다 작거나 같은 수의 갯수)이 k보다 작다면left 값을 올리고그렇지 않다면result 에 mid값을 대입한 후 right값을 내린다. #include using namespac..

문제보기현재 주사위 상단,하단 그리고 하단의 상,하,좌,우 에 무슨 숫자가 있는지 계속 갱신해가며 주사위를 굴린다. 굴리면서 문제에 명시된 규칙대로 칸에 있는 숫자를 주사위로 옮기거나 주사위 숫자를 칸으로 옮기면 된다. using namespace std;typedef enum{UP , RIGHT ,DOWN ,LEFT }dir;int bottom = 1,top = 6;int position[4] ={2,3,5,4};//up,right,down,left int setPosition(int n){ int tpB = bottom,tpT = top; switch(n){ case 1: bottom = position[RIGHT]; top = position[LEFT]; position[RIGHT] = tpT; p..

BFS를 사용하면 쉽게 풀 수있는 문제였다. 처음에 토마토가 비어있는 부분이 있으면 (배열중 들리지 않은곳이 있으면) 무조건 모두 익지 않은 경우라고 체크해서 -1을 출력하고 틀렸었다.처음 주어진 익은 토마토를 큐에 전부 넣는다 check[x][y]에는 토마토가 익은 날을 저장한다. 인접한 토마토는 check[x][y] 다음날에 익으므로check[nx][ny] = check[x][y]+1이다. check[x][y]중 가장 큰 수가 토마토가 모두 익은 날이다. #include #include using namespace std; int main(){ int box[1001][1001]; int check[1001][1001]; queue q; int N,M; scanf("%d %d",&N,&M); for(..