본문 바로가기
반응형

[백준]214

[BaekJoon/백준] 3085번 사탕 게임 정말 더 간단한 풀이는 없는 것인가 고민했는데, 찾아보니 없는 것 같다. '스왑하고, 검사'하고 를 반복하면 된다. 총 O(N^4) 정도 나오겠다. N이 50이니까 1초안에 해결은 된다. (간단한 연산을 컴퓨터는 1초에 1억번) #include #include using namespace std; int N; char MAP[50][50]; int MAX; // 시간복잡도 O(n^2) void EVALUATE() { int COUNT = 0; // 행마다 검사 for(int i = 0; i < N; i++) { COUNT = 0; for(int j = 1; j < N; j++) { if(MAP[i][j] == MAP[i][j - 1]) COUNT++; else COUNT = 0; if(MAX < COUN.. 2022. 7. 5.
[BaekJoon/백준] 2309번 일곱 난쟁이 나는 DFS로 9명의 난쟁이 중에 7명의 난쟁이를 뽑아서 계산했는데.. 다른분들의 풀이를 보니 더 간단한 방법이 있었다. 전체 난쟁이의 합을 계산한 다음, 둘을 뺐을 때 100이 되는 경우를 찾으면 되는 것이다. 즉, 내 풀이는 9C7이었는데, 위 방법은 9C2로 해결할 수 있었다. 그럼 DFS처럼 재귀로 하지 않고 반복문으로 해도 풀 수 있겠다. #include #include #include using namespace std; vector v; vector ans; // 조합을 이용해서 9개 중에 7개를 뽑는다. // 한 방향으로만 이동하니까, VISIT 확인은 굳이 해주지 않아도 될 거 같네. // 넣었다 뺐다 토글만 잘 해주면 된다. (push - pop) void dfs(int start) {.. 2022. 7. 5.
[BaekJoon/백준] 13901번 로봇 DFS로 풀이했다. 처음 제출했을 땐 틀렸는데, 주의할 점은 '로봇은 벽이나 방문한 지역, 장애물을 만나기 전까진 계속 같은 방향으로 이동한다' 는 것이다. 주석을 상세히 달아놓았으니, 이해에 도움이 될 것 같다!! #include using namespace std; int R, C, K; int START_X, START_Y; int MAP[1000][1000]; // 0은 미 방문, 1은 방문, 2는 장애물 int DIR[4]; // 값 => 1 : 상, 2 : 하, 3 : 좌, 4 : 우 // 상 하 좌 우 인덱스 : 0 1 2 3 int mx[4] = {-1, 1, 0, 0}; int my[4] = {0, 0, -1 ,1}; void dfs(int x, int y, int dir) { MAP[x.. 2022. 7. 5.
[BaekJoon/백준] 3048번 개미 다른분들처럼 깔끔하게 코드를 짜진 못했다. 하지만 시간복잡도는 더 절약한 것 같다. 아마 다른분들은 문자열에 방향성을 부여해서 0 : 오른쪽 이동, 1 : 왼쪽 이동으로 정의한 뒤에 000 111 001 011 010 101 101 010 이런식으로 해서 매 초 phase마다 포문을 돌리면서 '01' 을 찾으면 swap 해주는 방식을 사용하신 것 같다. => reverse()를 제외한 구현에서 O(T(n + m)) 시간복잡도 나는 시뮬레이션을 직접 돌려보면서, 규칙성을 찾았고 그걸 토대로 구현하였다. 시간복잡도면에서 내 구현이 더 빠르다고 생각한다. => reverse()를 제외한 구현에서 O(n + m)에 해결된다. #include #include #include using namespace std; .. 2022. 7. 4.
반응형

티스토리툴바