1. 문제  요약4와 7을 이용해서 K 번째 작은 수 만들기  2. 접근작은 수를 차례로 써보면  4,7,44,47,77,444,447,474...이다. 숫자만 다를 뿐 두 개의 수로 표현한다는 점에서 이진수를 표현하는 방법과 유사하다.k번째로 작은 수0과 1로 표기4 071440047017711444000447001474010 이 방법까지 떠올리면 반은 온거다. 하지만 이진 수랑 다른 점이 있다. 바로 맨 앞 bit에 0이 온다는 것이다. 최대한 이진수랑 연관시켜서 방법을 찾아야 한다. 이진수를 쭉 써보자 k번째로 작은 수0과 1로 표기이진수401711044001147011007711101444000110447001111 규칙이 있다. 잘 보면 k번째 작은 수는 k+1를 이진 수로 표현한 것에서 맨 앞..

1. 문제https://www.acmicpc.net/problem/21315 요약카드를 2번 섞은 후에 결과를 줄테니, 각 2번의 k 값을 구해라  2. 접근독해력이 안좋아서 문제 이해하기가 어려웠다. 아무튼 k의 값을 구하는 건데, 문제의 조건을 보면3 ≤ N ≤ 1,0001≤ K, 2K 로 k는 1~9의 값을 가질 것이다. 그리고 두 번만 수행하면 되니 최대 많아야 9*9 = 81번이니 완탐으로 접근한다. 최종 결과를 보고 처음 결과로 돌아가기(x)처음엔 입력으로 주어진 결과를 이용하여 연산을 거꾸로 해서 초기값을 찾고자 했다. 하지만 좋은 방법이 아니였다. 연산이 더 복잡해지고 생각할 것이 많아진다. 처음상태를 가지고 최종 결과와 비교하기(o)그래서 초기 값이 {1, 2, 3..., N} 순서로 주..

1. 문제https://www.acmicpc.net/problem/15661  2. 접근2개의 팀을 나누어서 전체 인원을 뽑는다.스타트 팀에서 N-1명을 뽑았으면, 링크 팀에서는 1명을스타트 팀에서 N-2명을 뽑았으면, 링크 팀에서는 2명을...스타트 팀에서1명을 뽑았으면, 링크 팀에서는 N-1명을 엇 근데 경우의 수가 너무 많은 것 같네. 이 방법이 아닌가 보다. 뭐지??? 도저히 모르겠다. 포기 접근은 맞았다. 근데 내가 경우의 수가 너무 많다고 생각한 이유는 한 팀을 결정 해놓은 상태에서 다른 팀을 구해야 하는 줄 알아서 AND 연산으로 착각을 했다. 또한 뽑은 인원을 관리할 방법이 생각이 안났다. 하지만 이 문제는 그렇게 푸는 것이 아니었다. 왜냐하면 한 팀에서 인원을 결정하면 자동으로 다른 팀 ..

1. 문제  2. 접근우선 그려봤다. N이 2일 때, 4일 때, 6일 때그려보니 4일 때 새로운 경우가 2가지 나오는 것을 알았다. 이것을 제외하면 dp[i-2]*3을 해주면 되는데, 새로운 경우를 어떻게 처리할지 몰랐다.  근데 N이 4일 때 말고도 6, 8... 이 될 때마다 새로운 경우가 아래 처럼 2가지 추가됐다.이 경우를 따로 구해줘야 한다.dp[0] = 1;dp[2] = 3;for(int i=4; i=0; j-=2){ dp[i] += dp[j]*2; }} 만약 내가 구하는 것이 dp[6]이라할 때, 우선 dp[4]에서 3을 곱한다. 왜 3을 곱하냐면 dp[2]가(3x2), 즉 3x2를 구성하는 경우의 수가 3이기 때문이다. 그래서 3x4를 이루는 블록에 3x2 블록을 붙여주는..

1. 문제  2. 접근문제 읽고 평소에 풀던 BFS 문제들이랑 비슷해서 별로 생각 안하고 풀다가 시간초과가 났다. 접근1. 모든 좌표를 다 돌면서 모래성(1~9)인 경우 주변(대각선, 상하좌우)을 체크한 후 무너지면 체크해주기, 그리고 체크 된 모래성들을 한 번에 0으로 표시하기 이렇게 풀었더니 시간초과가 났다. 로직에는 문제가 없는 줄 알고 모든 좌표가 아닌 -> 모래성 좌표만 큐에 저장해서 찾아가는 식으로 바꿔봤다. 하지만 이 방법도 시간초과가 났다. 시간 복잡도를 구해보니 모래성의 크기가 1000X 1000 = 10^6(백만)이고, 모래성의 개수가 평균 50%라고 했을 때 50만이고 BFS니깐 한 파도가 칠 때 평균 50만 * (8방향)이고 파도가 약 (Max(H, W) 이니깐 약 400,000만...