알고리즘/문제풀이 - 백준

백준 3190 뱀

문제 : https://www.acmicpc.net/workbook/view/1152 서론 시뮬레이션 문제이며 큐를 활용했다. 풀이 입력받으면서 회전은 큐에 저장하고 사과는 지도에 표시한다. 그리고 문제에 적혀진 매 초가 지날때마다 일어나는 행위들을 반복문에 쓴다. 뱀은 큐에도 저장하고 지도에도 위치를 표시했는데, 큐에 저장한것은 꼬리를 제거하기 위함이고 지도에 표시한건 자기 몸과 부딫히거나 벽과 닿는지 확인하기 위해서다. int dy[4] = { 0, 1, 0, -1 }; // 우하좌상 int dx[4] = { 1, 0, -1, 0 }; while (++time) { // 이동방향으로 한칸 이동 y = y + dy[dir]; x = x + dx[dir]; // 자기 몸과 부딫히거나 벽과 닿으면 끝 if..

2019. 10. 19. 15:46
알고리즘/문제풀이 - 백준

백준 14499 주사위 굴리기

문제 : https://www.acmicpc.net/problem/14499 서론 시뮬레이션 문제. 문제 이해가 필요하며 잘 읽어야한다. 주사위는 최초에 모든 면이 0이다. 전개도의 숫자가 아니다. 풀이 특정 방향으로 이동할때마다 전개도가 바뀌는데, 바뀐 전개도를 알면 나머지는 쉽게 구현 가능하다. 이동할때 바뀌는 전개도는 일일이 만들어가며 찾았다. 최초의 전개도 동 서 남 북 위 아래 3 4 2 5 1 6 각 방향으로 이동했을때 전개도 동 서 남 북 위 아래 최초 3 4 2 5 1 6 동 1 6 2 5 4 3 서 6 1 2 5 3 4 남 3 4 1 6 5 2 북 3 4 6 1 2 5 구현 // c++ #include #include using namespace std; int map[20][20]; i..

2019. 10. 19. 10:55
알고리즘/문제풀이 - 백준

백준 14503 로봇 청소기

문제 : https://www.acmicpc.net/problem/14503 서론 시뮬레이션 문제. 풀이 시뮬레이션 문제이므로 문제가 시키는대로 잘 따라간다. 편의를 위해서 문제를 한가지 수정한다. 문제에서는 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽이라고 하는데 0은 북, 1은 서, 2는 남, 3은 동으로 수정했다. 청소기가 오로지 왼쪽으로만 회전을 하는데 왼쪽으로 회전하면 d가 1 증가하므로 (d+1)%4 를 쓰기 위해서다. (d+1)%4 는 d가 0, 1, 2, 3, 0, 1, 2 ...로 0~3만 가지도록 한다. 문제를 수정했으므로 방향을 입력받을 때도 수정해줘야한다. dy[4] = { -1, 0, 1, 0 } dx[4] = { 0, -1, 0,..

2019. 10. 17. 21:51
알고리즘/문제풀이 - 백준

백준 14890 경사로

문제 : https://www.acmicpc.net/problem/14890 서론 정말 오래 걸린 문제. 3시간 넘게 푼것 같다. 시뮬레이션 문제라서 문제에서 시킨대로 풀면 된다. 버그 하나 뜨면 반복문과 조건문이 정말 많은데 중간에 나눌 수 있는 부분들도 아니라서 마치 엉킨 실타래 푸는 느낌이었다. 풀이 지도의 모든 열과 행을 조사해서 통과하는지 확인시켜주면 된다. 아래의 코드는 단 하나의 행이나 열이 통과하는지 확인하는 코드다. 이 코드에서 반복문이 얼마나 반복해야할지, 배열 인덱스의 정확한 위치 등 많은 조정이 필요하다. 이부분이 상당히 오래걸린다. void 확인(){ for(int i=0;i> n >> l; for (int i = 0; i < n; i++) { for (int j = 0; j < ..

2019. 10. 16. 22:32
알고리즘/문제풀이 - 백준

백준 14891 톱니바퀴

문제 : https://www.acmicpc.net/problem/14891 서론 시뮬레이션 문제. 시뮬레이션 문제는 정확한 문제 이해와 실수를 하지 않는게 정말 중요한데, 문제를 잘 못 이해했다. 모든 톱니바퀴가 돌기 전 상태에서 각각의 톱니바퀴 조건을 비교해야하는데, 1번 톱니바퀴가 회전하면 회전한 후의 상태로 조건을 비교해서 2번 톱니바퀴를 회전시키는 방식으로 이해했었다. 아이디어 회전할 톱니바퀴와 회전방향을 입력받으면 톱니바퀴들의 회전상태를 저장할 배열을 만든다. 회전할 톱니바퀴가 2번 톱니바퀴이고 회전방향이 오른쪽이라면 1 위와 같이 저장하고 오른쪽 톱니바퀴로 한칸씩 이동하며 회전가능한지 확인한다. 회전 가능하면 왼쪽 톱니바퀴의 -1을 곱한값을 입력한다. 회전할 수 없을때까지 반복한다. 1 -1..

2019. 10. 16. 14:03
알고리즘/문제풀이 - 백준

백준 15683 감시

문제 : https://www.acmicpc.net/problem/15683 서론 완전탐색 + 시뮬레이션 문제. 혼자 풀어내지 못했다. CCTV가 감시할 수 있는 모든 경우의 수를 재귀로 구현하려 했는데 재귀에서 리턴할때 해당 CCTV가 감시한 영역을 지워야한다. 이게 해결이 안되서 다른분의 코드를 봤다. 그리하여 탐색할때마다 현재 지도를 복사해서 리턴할때 복사한 지도를 불러오는 방법을 얻었다. 풀이 CCTV가 감시할 수 있는 모든 경우의 수를 얻어야한다. 그래서 재귀가 한단계씩 깊어질때마다 각 CCTV가 가질 수 있는 경우의 수를 재귀함수로 만들어준다. void dfs(idx){ if(idx == cctv개수) 0의 개수 계산 후 리턴 if(cctv == 1){ dfs(idx+1, 위쪽) dfs(idx..

2019. 10. 15. 16:51