댄코 - 댄싱코딩

문제보기두단계로 나눠서 풀이했다.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..

문제보기조건 1. 수평, 수직에 같은 숫자가 있는지 검사, 조건 2. 3x3안에 같은 숫자가 있는지 검사=> 3x3행렬의 첫 숫자는 x/3*3, y/3*3으로 구할 수 있음. map배열을 전부 돌면서 0인곳을 찾음,0인곳에 1부터 9까지 대입하며 위 두 조건으로 검사.맞는게 없으면 백트래킹 해서 다른 숫자를 넣어 다시 검사하기 위해 map[x][y]에 0을 대입한다.(0이 아니면 다른 좌표에서 검사할때 promising함수가 제대로 작동하지 않는다.) #include using namespace std;int map[9][9];void print_sudoku(){ for(int i = 0;i

문제보기수직으로 겹치지 않는지, 대각선으로 겹치지 않는지 검사한다.수평은 어차피 한줄씩 내려가면서 탐색하므로 겹치지 않는다. 현재 놓는 퀸이 전 퀸들과 겹치지 않는 위치라면 다음 줄로 내려가서 수평으로 한개씩 두어보며 위의 겹치는지 안 겹치는지 판단을 입력받은 N까지 반복한다. #include using namespace std;int N;int res = 0;bool check(int vec[], int newRow){ int curRow = 0; while(curRow < newRow){ if(vec[newRow] == vec[curRow] || fabs(vec[newRow]-vec[curRow])==(newRow-curRow)){ return true; } ++curRow; } return fals..

문제보기이분탐색으로 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..

문제보기붕어빵을 각 갯수 별로 한번에 판매할 수 있으므로,dp[i] = a[i]로 초기화를 해준다. i를 0부터 N까지 반복문 돌리면서 그안에서 j를 1부터 i-1까지 반복문을 돌리는데 그이유는 붕어빵을 살 수 있는 각 경우의 수 중 가장 큰 값을 도출하기 위함이다. 가령, i가 4이고 j가 1이라면 붕어빵 3개(i-j)를 팔면 남는 최대 수익(dp[i-j])에 붕어빵 1개(j)를 판 값을 더함i가 4이고 j가 2이라면 붕어빵 2개(i-j)를 팔면 남는 최대 수익(dp[i-j])에 붕어빵 2개(j)를 판 값을 더함i가 4이고 j가 3이라면 붕어빵 1개(i-j)를 팔면 남는 최대 수익(dp[i-j])에 붕어빵 3개(j)를 판 값을 더함 따라서 점화식은 다음과 같다. dp[i] = max(dp[i],dp[i..