열심히해보겠씁니다

CCTV 의 위치와 종류가 주어져있고, 방의 구조가 주어진다. CCTV로 감시할 수 있는 영역을 최대한으로 늘리는 것이 목표다. 문제의 조건은 다음과 같다. 1. 감시할 수 있는 부분을 최대한 늘릴 것 2. CCTV는 종류별로 감시할 수 있는 영역이 다르고, 방향 또한 바뀔 수 있다. 가령 1번은 오른쪽을 가리키고 있지만 돌려서 설치하면 위쪽을 감시하게 만들 수 있다. 문제의 접근 방식은 다음과 같다. 1. 완전탐색 문제의 해결방식은 다음과 같다. 1. CCTV를 돌려서 보는 방향을 바꿀 수 있다면 돌리면서 감시할 수 있는 영역을 확인한다. 2. 다른 CCTV에 대해서 1번을 수행한다. 방의 크기가 최대 8x8 이고 CCTV가 최대 8이므로 최악의 경우에도 6천가지 정도의 경우의 수를 탐색하면 된다. 고..

내 친구 호석이가 애벌레가 되어버린 문제이다. 호석이는 한 번 시작하면 특정 조건을 만족하기 전까지는 연속해서 먹이를 먹는다. 탙피 에너지를 최대한으로 축적하고 싶은데, 얼마나 축적할 수 있는지를 계산해보자. 문제의 조건은 다음과 같다. 1. 탈피 에너지를 최대한으로 쌓을 것 2. 먹이를 하나 먹으면 조건을 만족할 때까지 계속 먹을 것 문제의 접근 방식은 다음과 같다. 1. 먹이를 먹을 수도 안먹을 수도 있기 때문에 단순 루프로 접근하려면 케이스를 여러개 고민해줘야한다. 2. 애벌레의 다음 행동은 지난 행동에게 영향을 받는다. (직전 먹이를 먹었다 -> 조건 만족하면 멈추고 만족못하면 계속 먹어야함, 직전 먹이를 먹지 않았다 -> 이번 먹이를 먹을수도 안먹을수도 있다.) 3. 당장 최대한으로 만들 수 있..

백준 회사에서 축구대회를 한다. 팀원을 짜고 싶은데 시너지가 잘맞는 팀원이 있고 아닌 팀원들이 있어서 잘 짜야한다. 물론 재미있게 플레이하기 위해 전체적인 실력이 비슷해야한다. (20명인거보니 골키퍼는 고려안하나봐) 문제의 조건은 다음과 같다. 1. 두 팀의 능력치가 가장 비슷한 경우를 찾기 2. 두 팀의 인원은 같다.(N은 짝수) 3. 한 명이 특정 팀에 들어갈 경우 그 팀에 있는 모든 사람들과의 시너지를 계산해야한다. 전체코드 #include #include int N; int Min = 987654321; int Map[21][21]; int used[21]; int abs(int x) { if (x < 0) return -x; return x; } //시너지 계산 int check() { int ..

톱니바퀴를 빙글빙글 돌리는 문제이다. 문제의 조건은 다음 하나 뿐이다. 1. 특정 번호의 톱니바퀴를 돌릴 때, 바로 옆에 맞닿아있는 톱니바퀴와 다른 극으로 마주볼 때 같이 돌아간다. 주의해야할 점은 다음과 같다. 1. 1번 톱니바퀴를 돌렸을 때 4번 톱니바퀴까지 돌아갈 수 있다. 2. 1번 톱니바퀴를 돌렸을 때, 2번 톱니바퀴가 돌아가지 않으면 3번 톱니바퀴는 당연히 돌아가지 않는다. 3. 위, 오른쪽, 왼쪽 방향을 인덱스를 통해 가리키는 방법을 사용할 경우 돌리는 방향과 반대로 인덱스가 움직여야 한다. ex) 오른쪽으로 돌림 -> 위,오른쪽, 왼쪽 인덱스는 왼쪽으로 이동(-1) 3번은 다른 방법을 썼을 시 이해하기 어려우므로 코드를 참고하면 좋다. 문제 해결방식은 다음과 같다. 1. 톱니바퀴를 자석 상..

4x4 테트리스 업그레이드 버젼 같은 문제이다. 빨간 칸에 1x1 혹은 1x2 박스를 놓으면 각각 파란영역과 초록영역으로 떨어진다. 테트리스와 마찬가지로 각 영역에서 블럭이 쌓이는 방향에 수직인 칸 4개가 꽉차면 한 줄이 사라지면서 점수를 1점 얻는다. 또한 마찬가지로 깨진 칸 위에 있는 블럭들이 정확하게 한 줄만 내려온다. (빈 칸으로 찾아 떨어지지 않는다.) 특이한 점으로는 연한 영역에 블럭이 있을 경우이다. 모든 줄이 깨지고 나서도 연한 영역에 블럭이 있을 경우, 있는 줄의 수만큼 밑의 칸을 밀어버린다. 정말 간단한 문제이지만, 블럭이라는 구조체를 만들지 않고 그냥 맵에다가 뿌렸기 때문에 하드 코딩이 되었다. 케이스 별로 하나하나 코딩을 했기 때문에 굉장히.. 길지만 직관적이어서 접근하는데 좋았다...

경사로를 설치할 수 있는지 묻는 문제이다. 처음부터 끝까지 모두 부드럽게 연결되어야 하기 때문에 시작점은 y=0 이거나 x=0 인 지점부터 가로세로 한번씩만 하면 된다. 문제의 조건은 다음과 같다. 1. 높이차이는 1을 초과하면 안된다. 2. 경사로는 평평한 곳에만 놓을 수 있다. 3. 경사로의 길이만큼 놓을 땅이 필요하다. 4. 경사로는 겹칠 수 없다. 지도의 크기가 100x100 이므로 무리 없이 끝낼 수 있다. 문제 해결은 다음과 같다. 1. 현재보다 높은땅이 나오면 지금 땅에 경사로를 설치할 수 있는지 확인한다. 2. 현재보다 낮은땅이 나오면 다음 땅에 경사로를 설치할 수 있는지 확인한다. 3. 무리없이 설치하고 끝에 도착했다면 count한다. 두 방향을 하나의 함수로 만들 수도 있지만, 그냥 두..

문제에서 제시한 조건만 지켜서 탐색하면 완료되는 문제이다. 단, 처음 로봇방향을 제시하고, 로봇 방향기준 왼쪽부터 순차대로 탐색해야하므로 다음 탐색할 장소와 로봇 청소기 방향에만 신경써주자. 혹시 에러가 뜬다면 맵 크기나 범위 제한을 잘 해주자. 또한 종료조건이 단 하나 뿐인 것도 유념해두자. 전체 코드 #include int N, M; int Map[51][51]; int visited[51][51]; int r, c, d; int dy[] = { -1,0,1,0 }; // 0 : 북 1 : 동 2 : 남 3 : 서 int dx[] = { 0,1,0,-1 }; //d 기준 왼쪽은 d-1; int move() { int cnt = 0; int left = d-1+(d-1= 4) { left= d - 2 ..

아주아주 간단한 문제.. 인 줄 알았는데 2시간은 쓴 것 같다. 문제 자체는 아주 간단하다. 트리를 만들고 자르라는걸 자르고 leaf의 개수를 세면 된다. 틀린 지점은 3곳이다. 1. 0%에서 틀렸다면, 배열이 항상 0번 인덱스가 Root로 나오는 것은 아니라는 것을 파악하고 다시 코드를 짜야한다. 혹은 루트를 잘랐을 경우를 고려하지 않았을 수 있다. 다음 예시를 참고해보자 3 1 -1 1 0 정답) 1 3 -1 0 0 0 정답) 0 2. 77%에서 틀렸다면, 자식이 2개라고 생각하고 구현했을 가능성이 높다. 5 -1 0 0 0 0 3 정답) 3 3. 99%에서 틀렸다면 Root만 남았을 경우에 틀렸을 가능성이 높다. 5 -1 0 1 2 3 1 정답) 1 고생한 점은 다음과 같다. 1. 그림에 낚여서 자..

문제를 이해하기에 앞서 2048 (play2048.co) 를 한 번 해보면 좋다. 설명보다 훨씬 직관적으로 이해하기 편하기 때문. Easy 버전 답게 게임과는 다른 점이 있다. 1. 숫자는 초기 상태에서 추가되지 않는다. 2. 만들 수 있는 최대값만 알면 된다. 숫자가 추가되지 않고 움직이는 횟수가 적기 때문에 쉽다고 하는 것 같은데, 충분히 머리를 써야한다. 접근 방식은 다음과 같다. 1. 맵이 비교적 작고(20*20) 최대 5회까지만 움직이기 때문에 기껏해야 100만번의 경우를 완전탐색하면 된다. 해결 방식은 다음과 같다. 1. 현 상태에서 밀 수 있는 경우(좌우상하 네 가지) 중 하나를 수행한다.(DFS) 2. 최댓값을 갱신할 수 있는지 확인하고, 1번을 반복한다. 3. 5번 바꿀 경우 종료한다. ..

바다와 섬이 그려져있는 지도에 다리를 만들되, 다리를 최소한의 길이로 만들고 싶다. 조건은 다음과 같다. 1. 다리의 길이는 1보다 길어야한다. 2. 섬이 모두 연결되어야 한다. (연결 안될 경우 -1출력) 3. 다리는 일직선으로만 만들 수 있다. 4. 다리 양끝에 다리 방향으로 섬이 연결되어야 한다.(옆 방향에 붙는 것 안됨) 5. 다리는 교차할 수 있지만, 길이는 중복해서 센다. 가령 길이 3인 도로가 + 형태로 겹쳐있어도 길이는 6이다. 접근 방식은 다음과 같다. 1. 섬마다 번호를 매긴다. 2. 섬마다 만들 수 있는 다리를 모두 만들어 보고, 연결할 수 있는 섬과 그 때의 다리의 길이를 저장한다. 3. 최소 값으로 섬들을 연결시킨다. 4. 섬들이 모두 연결되어 있는지를 확인한다. 문제를 풀면서 고..