반응형 알고리즘/BOJ21 BOJ 15683) 감시 (C++) 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 각 CCTV의 좌표를 arr배열에 저장하고 가능한 모든 경우를 탐색한다. 5번 카메라는 한 방향, 2번 카메라는 2 방향, 나머지 카메라는 4 방향으로 설치가 가능하다. 풀면서 한가지 실수 때문에 시간을 많이 허비했다. 처음에 각 CCTV가 감시하는 공간을 -1로 체크하고 되돌아오면서 0으로 다시 복구시켜 준 것이다. 이렇게 할 경우 다른 CCTV와 같은 공간을 감시하다가 한 CCTV만 다른 방향으로 트는 경우에 해당 공간에 대한 감시가 풀린 것으로 체.. 2021. 9. 26. BOJ 16987) 계란으로 계란치기 (C++) 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 백트래킹을 이용해 풀었다. 1. 가장 왼쪽의 계란을 든다. 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다. 3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정.. 2021. 9. 24. BOJ 1941) 소문난 칠공주 (C++) 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에는 각 점에 대해 DFS나 BFS로 탐색을 시도하려고 했는데 그럴 경우 다음과 같은 경우가 탐색이 되지 않았다. O O O O O O O O O O O O O O 어떻게 해야 하나 머리를 싸매다가 https://transferhwang.tistory.com/294 님의 블로그에서 도움을 얻었다. 1. 7명의 학생을 뽑는다. 2. 해당 학생들 중 이다솜파가 4명 이상인지, 모든 학생이 인접해 있는지를 검사한다. #include using namespace std.. 2021. 9. 23. BOJ 4179 ) 불! (C++) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net BFS로 풀리는 문젠데 예외 처리 하는 부분에서 미처 고려하지 못한 부분이 있어 좀 헤맸다. 1. 불의 이동경로에 대한 큐와 지훈이의 이동 경로에 대한 큐를 각각 만들어주고 입력을 받으면서 시작점들을 각 큐에 입력해준다. 그리고 지훈이의 이동 시간을 체크할 배열(dist)과 불의 이동 시간을 체크할 배열(burn)에 이동 가능한 좌표를 -1로 체크해준다. (따로 체크하지 않은 좌표는 0으로 초기화 되어 있으므로 추후 방문여부 체크 시 해당 좌표가 .. 2021. 7. 28. BOJ 1012 ) 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net DFS로 간단히 해결 할 수 있는 문제. 왠진 모르지만 예전에 풀려고 시도했다가 실패한 흔적이 남아있었다. 벡터를 이용해 밭의 크기를 런타임에 지정해주고 배추는 1로 표시한다. 방문여부는 배추가 없는 곳은 방문할 필요가 없으므로 기본은 모두 0으로, 배추가 있는 곳은 배추 위치를 표시하면서 같이 방문여부를 1로 변경해준다. 그 이후에는 반복문을 돌면서 배추가 심겨진 곳을 dfs로 탐색한다. 다음 칸을 방문할지 말지는 배추가 있는지와 방문한적이 없는지를 모두 고려해준다. #i.. 2021. 3. 12. BOJ 1003 ) 피보나치 함수 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 간단한 DP로 해결할 수 있는 문제다. '피보나치 + 제한시간이 짧음' 에서 바로 DP가 생각나서 그렇게 풀었다. 그냥 피보나치문제를 풀 수 있다면 어려움 없이 풀 수 있는 문제. #include #include #define pii pair #define x first #define y second using namespace std; int T,N; pii fib[42]; void makefib(){ fib[0]={1,0}; fib[1]={0,1}; for(int i=2;i>T; makefib(); while(T--){ cin>>N; cout 2021. 3. 12. 이전 1 2 3 4 다음 반응형
