BOJ/C++ (202) 썸네일형 리스트형 [BOJ] 2636. 치즈 * 치즈가 없는 좌표(0)에서 탐색할 수 있는 곳에 (상하좌우) 치즈가 있는 좌표(1)가 있다면 -> 이번 타임에 녹는 치즈이다. * 큐를 돌고 있는 상황에서 치즈를 바로 없애버리면 (1-> 0) 한 타임에 모든 치즈가 녹아버린다. * 위 상황을 방지하기 위해 이번 타임에 녹은 치즈는 map에 -1로 표시한다. * 치즈의 개수를 셀 때 -1인 좌표를 0으로 바꾼다. (벡터에 넣어주고 그 좌표들만 0으로 바꿔줘도 되지만, 어차피 치즈 개수 셀 때 모든 맵의 좌표를 탐색하기 때문에 이 때 바꿔주는 것으로 했다.) * 치즈가 모두 녹아 없을 때까지 (check() == True) 반복한다. * 치즈가 모두 녹기 한 시간 전에 있는 치즈의 개수를 세야 하기 때문에 howmanyCheese()를 만들었다. 더 효.. [BOJ] 18808. 스티커 붙이기 *단순 시뮬레이션 *스티커가 회전한 결과를 미리 저장한다. sticker[100][4][10][10] 0: 0도 1: 90도 2: 180도 3:270도 *스티커가 순서대로가 아니라 조합을 구하는 건 줄 알고 시간초과를 걱정했는데 다행히 순서대로 붙이는 것이다. 스티커를 순서대로 불러오면서 4방향을 모두 본다. check() 에서는 지금 범위에 스티커를 붙일 수 있는지 없는지를 확인하고, 붙일 수 있으면 넣는다. 여러 곳을 붙일 수 있으면 가장 위쪽을 선택하는 것이기 때문에 그리디하게 해결할 수 있다. *스티커의 높이와 너비는 차지하는 칸과 동일하지 않기 때문에 sizes라는 백터배열에 저장한 후 가져왔다. *코드가 많이 더럽다. 시뮬레이션 문제이니, 풀이 방법만 참고하시길.. 더보기 #include #i.. [BOJ] 18809. Gaaaaaaaaaarden * 배양액들의 조합을 구해서 배치한다. * 큐를 [초록색 배양액, 빨간색 배양액] 으로 두 개를 사용하는데 depth와 좌표 정보를 넣었다. depth는 처음에 문제를 잘 못 이해해서 예시를 보고 추가했다. G 1 or 2 R 이렇게 되어있을 때만 가운데 좌표에 꽃이 필 수 있다. 동시에 도달했을 때의 정보를 넣어줘야 하는데 그 정보를 depth로 기록했다. *depth를 기록했다면 이 정보를 빠르게 찾아내야 하는데, 이 정보는 dp[][] 배열에 기록해서 빨간색 배양액이 다음에 갈 곳에 이미 초록색 배양액이 있다. -> dp[nx][ny] 가 depth + 1 이면 초록색 배양액이 방금 전에 도달한 곳이다라는 정보를 찾아낼 수 있다. -> 꽃을 틔운다. *50*50 인데 조합까지 해서 그런지 시간이 꽤.. [BOJ] 10799. 쇠막대기 (C) *스택 자료구조 구현 연습을 위해 C로 풀이 *() 는 레이저이므로 레이저가 나올 때마다 스택에 있는 [(] 의 개수만큼 더해준다. (쇠막대기가 잘라지니까) *[(]는 스택에 푸시 (레이저는 푸시 안함) *[)]는 스택에서 팝하는데 이때, sum++ 을 해줘야 한다. ((()())) 이렇게 있다면 보기 편하게 레이저를 *로 치환한다. ( (* *) ) 이렇게 될 것이다. 그럼 막대는 ( (* *) ) --- -> - - - ------ -> -- -- -- 이렇게 되는 데 레이저를 만날 때마다 스택에 있는 개수만큼 막대의 개수가 증가하게 된다. 막대의 끝을 의미하는 [)]가 나올 때는 나누어진 막대의 가장 오른쪽 개수를 세야 하기 때문에 sum++을 해준다. #include #include #includ.. [BOJ] 1158. 요세푸스 문제 (C) *큐 구현 연습을 위해 C로 품. #include #include #include //큐 구현하기 #define MAXX 5001 struct Queue { int num[MAXX]; int front, back; }; int isEmpty(struct Queue *q) { if (q->back == q->front) return 1; return 0; } int isFull(struct Queue *q) { int tmp = (q->back+1)%MAXX; if (tmp == q->front) { //back+1 을 MAXX로 나눈 값이 front와 같으면 //가득 차 있다. return 1; } return 0; } void push(struct Queue *q, int data) { if (isFu.. [BOJ] 2151. 거울설치 + TC *거울이 [\] [/] 이 두 방향으로 있다고 생각하고 풀어야 한다. 처음에는 45도이기 때문에 [/] 만 생각하고 풀었다가 아니라는 것을 알게 됐다. *처음 [#] 좌표에서 출발해서 4방향 모두 큐에 넣는다. *각 방향으로 한 칸 앞으로 전진한 좌표가 거울이면 방향을 바꾸어서 큐에 넣고, 방향을 바꾸지 않는 상태로도 큐에 넣는다. 이 좌표에 거울을 설치하지 않는 경우도 생각한다. 3 ... *!# #!! 이 예시를 보면 (1, 3)에서 출발해서 (3,1)로 가야하는데 남쪽 방향으로 (3,3)의 거울로 간 후, 방향을 한 번 바꾸면 바로 (3,1)에 접근가능하다. #include #include #include #include #include #define INF 987654321 using namesp.. [BOJ] 9376. 탈옥 *세 지점에서 bfs를 실행한다. 상근이(0,0) / 죄수 2명 *상근이는 건물 밖을 마음대로 나다닐 수 있기 때문에 맵의 크기를 0,0~h+1, w+1으로 잡아줘야 한다. *상근이를 포함한 각 죄수들이 건물 밖으로 향하는데 여는 문의 개수를 dist[][]에 저장한다. *각 죄수들이 문을 열고 나가도록 코드를 작성하지만 실제로는 상근이가 두 죄수를 데리고 가기 때문에 세 명 다 문을 열 수 있는 가능성을 없애줘야 한다. (정답으로 요구한 것은 최소값이기 때문에) #include #include #include #include #include /* BOJ 9476.탈옥 */ using namespace std; int h, w; char map[102][102]; typedef pair pp; typed.. [BOJ] 12094. 2048(Hard) *2048(easy)와 풀이단계는 비슷하지만, 가지치기를 해줘야 한다. (최대 횟수가 2배로 늘었기 때문에) -가지치기 1) 변경된 맵이 변경되기 이전의 맵과 동일한 경우 -> 이 방향으로는 더 이상 나아가지 않는다. 2) 맵에서 최대값을 찾을때, 최대값은 2승씩 커진다. (cnt==10 이라면 가장 최대값은 1024가 될 것이다. ) 이 특징을 이용해서 현재 depth에서 최대값에 도달할 수 있는 지 확인한다. (즉, 한 번 10번까지 변경된 맵에서 최대값을 추출한 후 maxBlock[10] = 1024 / maxBlock[9] = 512 .... 이런 식으로 미리 저장을 해 놓는다.) *실제 최대값은 1024가 아닐 수 있다. 3) 현재 맵에서 구한 최대값이 현재 depth(==cnt)에서 나와야 하.. 이전 1 2 3 4 5 6 ··· 26 다음
