열심히해보겠씁니다

악명 높은 삼성 기출문제이다. 시간 단위가 0.5초 (가는 길에 서로 마주보는 다른 원자와 충돌하는 경우) 이기 때문에 상당히 어려운 문제다. 사실 겁나 어렵다. 더 밑의 차수를 보면 메모리 초과도 있다. 조건은1 4000 || ny 4000 || nx < 0) { at[i].y = ny; at[i].x = nx; continue; } //움직일 수 있는 원자 +1 num++; //만약 어떤 원자가 먼저 왔었다면 if (map[ny][nx]) { //먼저 온 원자 에너지 + ret+=at[map[ny][nx]].K; //방금 도착한 원자 에너지 + ret += at[i].K; //먼저 온 원자 에너지 0 (충돌 끝) at[map[ny][nx]].K = 0; //방금 도착한 원자에너지 0..

스마트하고 그리디한 택시기사를 위한 문제이다. 문제의 조건은 다음과 같다. 1. 가장 가까운 승객을 태운다.(여러명일 경우 y가 가장 작은 승객, y가 같은 경우 x가 가장 작은 승객을 먼저 태운다) 2. 승객을 목적지 까지 태워준다. 3. 연료는 1칸 이동할때마다 1씩 닳는다. 4-1. 승객에 도착하기 전 연료가 다하거나 목적지에 도착하기 전 연료가 다하면 -1을 출력한다. 4-2. 승객을 모두 태우기 전에 종료되면 -1을 출력한다. 5. 도착지에 도착하면, 승객을 태운 위치에서부터 걸린 시간(이동한 칸 수)의 2배만큼의 연료를 충전한다. 6. 모두 태우고 나서 남은 연료의 양을 출력한다. 7. 벽은 지나가지 못한다. 문제의 접근 방식 및 해결방식은 다음과 같다. 1. 가장 가까운 승객을 찾는다.(BF..

홀수 중독자 호석이 이야기다. 주어진 10^9 이하의 숫자를 쪼개고 쪼개서 홀수를 가장 많이 보고 싶다고 한다. 문제의 조건은 다음과 같다. 1. 마지막 한 자리만 남기 전까지의 과정에서 가장 홀수를 많이 보는 경우와 적게 보는 경우를 구한다. 2. 시작 숫자부터 중간과정의 숫자에서 나타나는 모든 홀수를 세지만 마지막 한 자리만 남았을 때는 세지 않는다. 3. 두 자리 숫자는 두 개로 나누면 되지만, 수가 세 자리 이상일 경우 임의의 자리에서 '알아서' 잘라서 3종류의 숫자로 만들어서 다 더해서 다음 숫자를 구한다. 문제의 접근 방식 및 해결방식은 다음과 같다. 0. 완전탐색 1. 자릿수마다 처리하는 방식을 다르게 한다. 2. 세 자리가 넘어가는 수를 다룰 때는 자를 위치를 두 곳 정하고 다음 숫자를 구..

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 ..