synodic의 삭망월

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 브루트포스로 해결한다 하더라도 시간복잡도는 O(NM)이다. 가능한 모양의 개수 19개를 N*M개만큼 적용하는 것이다! 그러므로 맘 편하게 브루트포스로 해결했다. 다른 풀이를 찾아보니 depth를 5로 정하여 탐색하는 방법도 있는 듯하다. #include #include #include #include using namespace std; // O(NM) const int MAX = 500; int..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 중간에 실수를 많이해서 한시간 반-두시간을 붙잡고 있었다. ㅠㅠ 1. x를 전역변수로 선언해놓고 go()라는 함수에서 지역변수로 또 사용했다. 2. 좌우로 이동하면 y가 증감하도록 해야하는데 내 머릿속 좌우 == 2차평면위의 x축인 나머지 x를 증감하는 실수를 했다. 거의 단순 구현이니 못 풀었다해도 이 글을 읽되, 코드는 최대한 나중에 참고하고 풀어보길 바란다! 문제를 다 풀고 난 뒤 다른 사람들이 푼..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net Bead라는 structure를 만들고, 처음 구슬들의 위치를 기록해 queue에 push한다. 이후 bfs로 탐색하는데, 핵심은 파란 구슬과 빨간 구슬이 동시에 구멍에 빠질 때이다. 이것을 떠올리지 못해 풀이를 참고했다. ㅠㅠ 또 이동하려는 다음 위치가 벽이 아니고, 현위치가 구멍이 아닐 때만 이동할 수 있다. 이 점도 실수했다. 나중에 꼭 다시..

아이디어 명령어 입력 전후를 구분하여 주사위에 새겨질 값을 바꿔야하기 때문에 dice[]배열과 new_dice[]배열 두개를 선언한다. 입력된 명령어가 1,2,3,4인 경우 각각 dice[] 및 지도 arr[x][y] 배열을 조건에 맞게 기록한다. 문제에 힌트가 주어졌다. 위 숫자들을 dice[] 및 new_dice[]의 index라고 생각하자. new_dice[]라는 지역 변수에 직전의 주사위 값인 dice[]의 값을 기록한다. 그리고 x또는 y의 값을 증감하여 다음에 탐색할 지도의 위치를 찾는다. 이때, 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안 된다. 라고 했으므로 매 명령어마다 실행하려는 x 또는 y의 증감이 지도의 범위를 벗어나는지 체크해야한다. new..