코딩하기 좋은날

이 문제는 빌딩을 세워놓고 왼쪽에서 봤을 때 보이는 개수와 오른쪽에서 보이는 개수가 주어진 경우 이를 만족하는 빌딩의 조합이 몇개 있는지 찾는 문제입니다. 높이가 제일 높은거부터 세우고 차례대로 하나씩 세우는 식으로 처음에 생각을 했는데 뭔가 잘 안떠올라서 힌트를 조금 보고 해결했습니다. 결론적으로 높이가 N인 빌딩 까지 세우고 그다음 높이가 N-1인 빌딩을 세운다고 하면 3가지의 경우로 나눌 수 있습니다. 1. 가장 왼쪽에 세우는 경우 2. 가장 오른쪽에 세우는 경우 3. 현재 있는 빌딩들 사이에 세우는 경우 1번의 경우 왼쪽에서 바라보는 개수가 하나 증가합니다. 2번의 경우 오른쪽에서 바라보는 개수가 하나 증가합니다. 3번의 경우 개수의 변화가 없습니다. (N-1 은 현재 가장 작은 빌딩이므로) 1,..

우선 계단 수는 각 자리 수가 모두 1씩만 차이가 나는 수입니다. 아마 이계단 수들의 경우의 수만 구하는 문제도 있는 걸로 알고 있습니다. 그럴 때는 i자리 숫자의 맨앞자리 수를 담은 dp 배열을 통해서 쉽게 해결 할 수 있습니다. 이 문제는 한가지 조건이 더 있습니다. 이러한 계단 수중 0~9 까지의 숫자가 모두 사용 된 경우의 수를 구해야 합니다. 그렇다면 우리는 i 자리의 수가 어떤 수들로 이루어져 있는가?라는 추가 정보를 저장해야 합니다. 잘 생각해보면 숫자는 결국 10개 밖에 없습니다. 이런 식의 체크를 할때 유용하게 쓸 수 있는게 비트마스크를 이용해서 체크하는 것이죠. 외판원 순회에서 비트마스킹을 이용한 dp를 한적이 있습니다. 2^10은 1024니까 메모리 걱정도 없습니다. dp배열의 의미는..

이 문제는 로봇이 1,1에서 N,M까지 가는데 왼쪽,오른쪽,아래로 갈 수 있고 한번 방문한 곳은 못갈 때 최대 값을 구해야 하는 문제입니다. N,M의 제한이 1000이므로 모든 경로를 다보는 것은 1000^3으로 불가능 합니다. 따라서 dp를 이용하여야 하는데 우선은 i,j에서 다음 경로로 이동 할 때 전에 어디서 왔느냐에 따라 갈 수 있는 곳이 제한 됩니다. 예를들어 i,j의 값이 i,j-1에서 온 값이라면 왼쪽 이동이 불가능 합니다. 따라서 dp를 3차원배열로 만들고 풀었습니다. dp[i][j][k] = i,j에서 이전에 k방향에서 왔을 때의 cost 이후 쭉 돌면서 i,j에서 갈수 있는 값을 갱신 시켜 줍니다. 이때 각 행에 대해서 왼쪽에서 오른쪽으로 먼저 진행을 해주고 반대로 오른쪽에서 왼쪽으로도..

선분이 이전 모양의 90도 회전한 모양이 덧붙는 형식입니다. 저는 그냥 그림을 보다가 이전세대 모양이 90도 회전하여 붙는 것이므로 이전 세대의 끝점에서 뒤로 가며 나오는 방향의 90도 회전한 방향의 좌표를 추가해주는 식의 재귀함수로 세대를 구한다음 체크하였습니다. 사각형의 개수는 각좌표의 4방향이 모두 1이면 체크 해주는 식으로 진행을 하면 됩니다. 다음은 코드입니다. #include using namespace std; int visited[110][110]; void check(vector dir, int cnt) { if(cnt == 0) { for(int i = 0; i < dir.size(); i++) { int x = dir[i].first; int y = dir[i].second; visi..

이 문제는 주어진 사다리 형태에서 가로 사다리를 최대 3개까지 추가해서(그 중에 최소) i번째 사다리가 i번째에 도달하는 형태를 만들 수 있는지 찾는 문제입니다. 따라서 각 경우 i번째에 도달하는지 검사를 하는 함수와 각각 0~3번 사다리를 추가하는 함수를 실행시켜 되는 경우가 있는지 확인해 주면 됩니다. 이때 연속되게 다리를 놓는것은 불가능하므로 현재 보는 구간과 이전 구간 이후 구간에 사다리가 없는지 모두 확인 한뒤 그렇다면 다리를 놓으면 됩니다. 즉 다리를 0~3개 까지 추가하는 함수를 실행시킨뒤 그함수가 다리를 추가시켰을때 i번째 사다리가 i번째에 도달 한다면 그 사다리를 추가시킨 횟수가 답이 됩니다. 다음은 코드입니다. #include using namespace std; int ladder[3..

브루트 포스 문제입니다. 5가지 종류의 cctv가 있고 이 cctv는 벽이 없다면 해당방향을 감시 할 수 있게 됩니다. 각 주어진 cctv는 회전하여 설치가 가능할 때 사각지대의 최대 영역을 구하는 문제입니다. 따라서 각 cctv가 탐지 할 수 있는 부분을 90도씩 회전해서 감시해보고 각 상태에서 사각지대 영역을 구해서 답을 구하면 됩니다. 다음은 코드입니다. #include #include using namespace std; int cctv[10][10]; int N,M; vector pos; int c1[4] = {1,0,0,0}; //상좌하우 int c2[4] = {1,0,1,0}; int c3[4] = {1,1,0,0}; int c4[4] = {1,1,1,0}; int c5[4] = {1,1,1..

이 문제는 각 행과,열을 길이라고 할 때 지나갈 수 있는 길의 개수를 구하는 문제입니다. 길을 지나간다는 것은 높이가 같은경우 통행이 가능하고 만약 높이가 정확히 1차이난다면 문제에 주어진 길이 L만큼의 경사로를 설치 할 수 있습니다. 이 경사로를 배치하면 그 구간은 지나갈 수 있게 됩니다. 이때 이 경사로는 높이가 더 낮은 곳에만 설치 할 수 있습니다. 즉 정리하면 각 행과 열을 훑어보면서, 높이가 1차이 나는 순간 높이가 더낮은 바닥이 최소 L이상 존재하는지 확인 해주면 되는 문제입니다. 구간을 보면서 현재 연속된 구간의 개수인 curlen을 추가해주며 진행해줍니다. 이때 높이가 1 차이나는 순간을 만났을 때 만약 전에 본 부분이 높이가 낮다면 curlen 이 주어진 길이 L보다 크거나 같은지 확인 ..

이 문제는 해당판에 주어진 5개의 테트로미노를 회전,대칭을 포함해서 놓았을때 가장 큰 값을 구하는 문제입니다. 원하는 테트로미노 모양마다 각칸에 넣어보면 되는 브루트 포스 문제입니다. 그렇다면 존재하는 모든 테트로미노의 모양을 구하는게 핵심인데 ㅗ ㅓ ㅏ ㅜ 이모양 말고는 dfs로 만들 수 있습니다. 그런데 사실 모든 경우를 따져봐도 19가지? 정도가 나와서 저는 그냥 모든 모양을 다 넣었습니다. 문제의 의도는 dfs를 이용하는 것이겠지만 그냥 뭐 이렇게 해도 풀리긴 합니다~. 물론 모양이 더많아지면 이렇게 하면 너무 힘들겠죠,, 다음은 코드입니다. #include using namespace std; int board[510][510]; int one[2][4][4] = { { 1,1,1,1, 0,0,..