본문 바로가기

boj19

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.

BOJ 5829 ) Luxury River Cruise 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1 >K; river=vector(N+2,vector (2)); int L,R; for(int i=1;i>L>>R; river[i][0]=L; river[i][1]=R; } char temp; for(int i=0;i>temp; if(temp=='L')seq.push_back(0);// L else seq.push_back(1);// R } cout 2020. 9. 22.

BOJ 5980 ) Corn Maze 5980번: Corn Maze This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both www.acmicpc.net 텔레포트가 있는 미로를 탈출해야 한다. BFS문제인데 텔레포트를 밟는 계산을 고려하는게 좀 어려웠다. 일단 최단경로를 구하는 문제라서 같은 길을 두번 거치면 무조건 거리가 증가해서 visited.. 2020. 9. 20.

이전 1 2 3 4 다음

티스토리툴바