댄코 - 댄싱코딩

문제보기현재 주사위 상단,하단 그리고 하단의 상,하,좌,우 에 무슨 숫자가 있는지 계속 갱신해가며 주사위를 굴린다. 굴리면서 문제에 명시된 규칙대로 칸에 있는 숫자를 주사위로 옮기거나 주사위 숫자를 칸으로 옮기면 된다. 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(..

그래프에 있는 사이클을 구하는 문제다.i번째 인덱스를 고정해놓고 1 부터 검사한다. j = arr[i]로 초기화하고 이때 j(다음으로 이어질 숫자) 와 i(사이클의 첫번째 숫자)가 같을 때까지 j = arr[j]로 업데이트한다. 검사한 인덱스 에는 1을 대입해 중복 검사를 하지 않도록 한다. j 와 i 가 같아지면 순열 사이클이 형성된것이므로 res에 1을 추가한다. #include using namespace std; int main(){ int T,N; int arr[1000]; int check[1000] = {}; int j = 0,res = 0; scanf("%d",&T); while(T > 0){ res = 0; j = 0; scanf("%d",&N); for(int i = 1;i

개미를 실제로 움직이며 시뮬레이션 해봤는데 시간초과가 떴다. 그리고 개미가 마주보면 무조건 뒤 돌게 되는데 문제에 한점에서 겹쳤을 때 뒤 돈다고만 적혀있어서 헷갈렸다. 규칙이 있는데 말로 설명하기가 좀 어렵다.개미가 한점에서 마주쳤을 때 개미는 서로 처음에 주어진 막대로 떨어지기까지 거리를 맞 교환하게 된다. 따라서 처음에 주어진 거리에서 아이디가 양수면 오른쪽끝과 현재 포지션사이의 거리아이디가 음수면 왼쪽끝과 현재 포지션사이의 거리를 정렬하면 개미가 떨어지기까지 거리를 알 수 있다. 또한 막대 맨 왼쪽 또는 오른쪽에 있는 개미가 우선적으로 떨어지게 된다. 정렬된 개미 배열에서 거리가 가장 적은 개미 부터 검사해서개미의 아이디가 양수면 맨 오른쪽 개미가 떨어지고개미의 아이디가 음수면 맨 왼쪽 개미가 떨어..

https://www.acmicpc.net/problem/1024 처음에 나누는 수 L을 짝수일 때, 홀수일 때로 나눠서 나온 수를 수열의 가운데 있는 숫자라고 정하고,그 수 앞뒤로 연속되는 숫자를 출력하는 방식으로 했는데 94%에서 틀렸습니다가 나왔다. 반례는 찾지 못했다. 수학적 지식이 있으면 쉽게 풀 수 있는 문제였다. 우선 N 은 길이가 L인 연속된 수의 합이다. 여기서 수열의 처음 시작인 x와 L을 알면 수열 리스트를 알 수 있다.x를 구하기 위해서 다음과 같은 식을 세울 수 있다. 여기서 t는 1부터 L-1 까지의 합 (L-1) * L / 2의 식을 사용하면 쉽게 구할 수 있다. 이때,x는 0보다 커야 하고,N-t는 L로 나눈 나머지가 0이어야한다(정수). #include using names..

2017/07/01 - [코딩/알고리즘] - [2293] 동전1 이문제는 동전1과 같은 문제라고 생각해서 그렇게 풀었는데 아니었다.동전1은 2+1과 1+2를 같다고 보지만,이문제는 두개를 다른 경우로 보기때문이다.사실 동전1에서두개의 포문 위치만 바꿔주면 된다. 구할 숫자에 대한 포문이 바깥이고 그 값을 1,2,3으로 만드는 경우의 수를 안쪽 포문으로 돌리면 중복은 고려치 않고 1,2,3값을 계속 d[j]에 추가해주기 때문이다. 동전1에서는 1,2,3으로 만드는 경우의수 포문이 바깥에 있었기때문에 중복없이 경우의 수를 구할 수 있었다. #include using namespace std; int main(){ int N, T = 0; int d[12]; scanf("%d", &T); for (int k ..

알고리즘을 전혀 모를때 알만툴에서 이미지로 점수 표시해 보겠다고 숫자의 각 자릿수의 숫자를 구한적이 있었는데, 이번에야 식을 알아냈다. i 자리의 숫자를 알아내려면 number = total % pow(10,i) / pow(10,i-1) #include #include using namespace std; int main(){ int A,B,C =0; int total = 0; int num[11] ={}; scanf("%d %d %d",&A,&B,&C); total = A*B*C; int tp = 0; for(int i = 1;i

처음에 이진수 오타인줄 알았다. dp에 좀 더 익숙해 지기위해서 dp로 풀어보았다.한번 틀렸던게 N으로 90이 들어오면 int범위를 넘어간다. dp문제를 풀때는 자료형도 주의해야겠다.d[i][0]에는 i 번째 자릿수인 이친수의 끝자리가 0인 이친수,d[i][1]에는 i 번째 자릿수인 이친수의 끝자리가 1인 이친수를 저장했다. i번째 자릿수인 이친수의 끝자리가 1이려면 i-1자릿수인 이친수의 끝자리가 0이어야 한다.∴ d[i][1] = d[i-1][0] i번째 자릿수인 이친수의 끝자리가 0이려면 i-1자릿수인 이친수의 끝자리는 0또는 1이어야 한다.∴ d[i][0] = d[i-1][0] + d[i-1][1] 이 식을 1부터 N까지 돌리고d[N][0]과 d[N][1]을 더하면 N번째 자릿수인 이친수의 갯수가..

피보나치 수를 디피 탑다운 방식으로 풀어보았다.fibo 함수를 재귀로 부르면서 dp테이블에 값을 저장한다. 이때 dp[n]의 값이 이미 존재한다면 이전에 계산한 값이므로 dp[n]을 바로 리턴한다. 그렇지 않다면 n==0일때 0, n 0){ return dp[n]; } if(n == 0){ dp[n] = 0; }else if (n < 3){ dp[n] = 1; return 1; }else{ dp[n] = fibo(n-2) + fibo(n-1); } return dp[n];} int main(){ int N = 0; scanf("%d",&N); printf("%d\n",fibo(N));}

처음에 C++쓰는 김에 배열을 사용해서 circleQueue 클레스로 만들어보자 했는데 계속 틀렸습니다가 떴다.반례를 못찾아서 다시 덱으로 구현했다.덱의 맨 앞부분의 숫자가 현재 찾고자 하는 숫자와 같으면 덱에서 pop()아니라면 현재 찾고자 하는 숫자의 인덱스가 앞쪽에 가까운지, 뒤쪽에 가까운지 검사앞쪽에 가까우면 덱의 맨 앞 원소를 덱의 맨 뒤로,뒤쪽에 가까우면 덱의 맨 뒤 원소를 덱의 맨 앞으로 옮긴다.위 과정을 입력받으로 받은 큐가 빌 때까지 반복한다. #include #include #include using namespace std; deque dq;int getIndex(int n){ int ret = 0; for (int i = 0; i < dq.size(); i++) { if (dq[i]..