문제https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu풀이내가 생각할 때 이 문제에서 중요한 점은 이전에 탐색했던 방향과 반대 방향으로 가지 않는 점과 모든 방향은 한번씩만 사용되는 점 같다.방향에 따른 dx, dy를 저장했고 모든 점을 출발점으로 시작시켜보고 가장 큰 값을 저장했다.초기 시작 방향은 4가지 방향 모두 다 해보는 것이 아니고 오른쪽 아래만 해봐도 모든 경우를 탐색할 수 있기 떄문에 오른쪽 아래만으로 잡았다.소스코드#include #include #include using namespace std; #define MAX_N 21 #define MIN_INF -98765..
문제https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu풀이굉장히 오래 걸린 문제다. 처음 접근은 Dfs를 돌며 이차원 행렬을 넘겨주는 식으로 구현했었는데 이렇게 되면 항상 성능검사를 해야돼서 구현이 정말 복잡했다.성능검사를 하는 구현도 복잡해서 잘 못했고 재귀함수도 올바른 방법으로 구현을 하지 못했던 것 같다.결국엔 해설을 찾아보고 이해가 쉽게 가는 방법으로 다시 코드를 짜봤다.일단 Dfs로 모든 행을 하나씩 돌아보며 i-1 번째 행까지의 연속된 셀의 개수를 세고 k개 이상이면 그 열의 성능검사가 통과했다는 것을 저장해서 넘겼다.해당하는 열이 성능검사를 통과 했는지의 여부는 비트마스..
문제https://www.acmicpc.net/problem/13460풀이Dfs를 통해서 기울이는 모든 방향을 탐색해야된다.이 때 주의할 점은 아래와 같다. 이전의 기울인 방향으로는 다시 기울이지 않는다.이전의 기울인 방향의 반대 방향으로도 기울이지 않는다 (원점이 되기 때문에) 원래는 2048 처럼 기울이는걸 구현하려고 했지만 빨간공과 파란공의 우선순위 비교까지 하려면 너무 복잡해져서 포기하고 답을 찾아봤다.여러 사람들이 빨간공 따로 파란공 따로 그냥 구현했고 위치가 똑같을 때만 우선순위를 비교해 다시 이동시키는걸 확인했다.삼성 기출문제 중에 가장 난이도가 높은 문제 같다.실제로 시험에서 이런 Dfs + 구현 문제가 나오면 풀지 못할 것 같다.소스코드#include #include using names..
문제https://www.acmicpc.net/problem/12100풀이제일 싫어하는 구현문제다. 중간에 큐 사용에 대한 오류가 떴는데 중단점을 이상한 곳으로 찍어놓고 디버깅을 돌려서 해결하는데 너무너무 오래걸렸다.위, 아래, 왼쪽, 오른쪽 모든 방향을 Dfs를 통해 완전탐색하면 되는 문제다.문제의 핵심은 주어진 조건에 맞게 한 쪽 방향으로 이동한 경우를 만드는 점이다. 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 이와 같은 조건 때문에 0이 아닌 수를 큐에 저장하는 순서는 아래와 같이 된다.방향이 위인 경우 (0,0) ~ (N-1,0) 방향이 아래인 경우 (N-1,0) ~ (0,0) 방향이 왼쪽인 경우 (0,0) ~ (N-1,0) 방향이 오른쪽인 경우 (N-1,0) ..
문제https://www.acmicpc.net/problem/14500풀이테트로미노의 종류는 총 5가지이지만 Dfs를 통해 탐색을 할 수 있는 경우는 4가지다.ㅗ모양은 Dfs로 탐색을 할 수 없기에 따로 탐색하는 함수를 만들었다.이 경우에는 인접한 칸을 모두 검사했을 경우 그 중에 가장 작은 값을 빼서 최대값을 구하는 방법으로 구현했다.처음에 접근을 테트로미노마다 다른 Dfs를 만들어서 각각 다른 회전을 써야되나 싶어서 어려워한 문제다.문제를 좀 더 쉽게 풀 수 있는 방법부터 생각해보는 게 좋을 것 같다.소스코드#include #include using namespace std; #define MAX_SIZE 501 #define MIN_INF -987654321 #define MAX_INF 987654..
문제https://www.acmicpc.net/problem/14499풀이처음에는 주사위를 굴릴 때 윗면과 바닥면만 바뀌는걸로 생각하고 시작했다.문제에서 전개도를 준 점을 생각해보니 이동할 때마다 주사위의 상태를 바꿔줘야했다.주사위를 정육면체라고 생각하고 cube[6] 을 만들어 각 면의 정보를 저장했다.이동할 때 상태변화는 다음과 같다.# 동쪽으로 이동하는 경우 이전 칸에서의 오른쪽 면이 현재 칸에서의 바닥면이 된다.이전 칸에서의 왼쪽 면이 현재 칸에서의 윗면이 된다.이전 칸에서의 바닥면이 현재 칸에서의 왼쪽 면이 된다.이전 칸에서의 윗면이 현재 칸에서의 오른쪽 면이 된다.# 서쪽으로 이동하는 경우 오른쪽 -> 윗면왼쪽 -> 바닥윗면 -> 왼쪽바닥 -> 오른쪽# 북쪽으로 이동하는 경우 앞쪽 -> 윗면뒤..
문제https://www.acmicpc.net/problem/3190풀이DFS를 통해 게임을 진행하는 식으로 구현했다. 게임의 규칙은 다음과 같다. 뱀은 매 초마다 이동을 한다.뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킨다.만약 이동한 칸에 사과가 있었다면, 그 칸에 있던 사과를 먹고 꼬리는 움직이지 않는다.사과가 없는 빈 칸이었다면, 꼬리를 이동시켜 다음 칸으로 간다(몸길이는 변하지 않는다.) 규칙에서 중요한 점은 아래와 같다. 사과가 없는 빈 칸을 이동할 때 꼬리였던 칸은 다시 빈 칸으로 만들어줘야 한다.방향에 따른 dx, dy를 만들어줬으며 map을 이용해 시간에 따른 뱀의 방향전환 상태를 저장했다.현재 시간에 해당하는 key가 map에 존재하면 그 value에 따라 뱀의 방향을 바꾸는 식으로 구..
문제https://www.acmicpc.net/problem/14501풀이삼성 기출문제 중에 난이도가 낮은 편에 속하는 것 같다.N의 범위가 작기 때문에 완전탐색으로 풀었다.오늘 예약된 상담을 진행하느냐 안하느냐 두 가지로 나누어서 재귀호출을 진행하면 된다.계속 재귀함수의 조건이 헷갈려서 많이 틀렸다.curr_day 가 n일 때 끝내는 이유는 curr_day가 n-1이고 상담에 걸리는 기간이 1일이면 하루만에 끝내고 수익을 얻을 수 있기 때문이다.소스코드#include #include #include using namespace std; #define MAX_SIZE 16 int n; int ans; vector vec_tp(MAX_SIZE, make_pair(0, 0)); void Recur(int c..
문제https://www.acmicpc.net/problem/14891풀이2시간 정도만에 주어진 테스트케이스 4개를 맞춰서 좋아한 문제다. 이상하게 계속 틀렸습니다가 뜨는데 몇시간동안 들여봐도 어디서 잘못된건지 몰랐다.지금도 뭐가 다른지 모르겠다.문제에서 톱니바퀴를 회전하는 부분을 보고 톱니바퀴의 정보를 덱(Deque)으로 저장했다.문제에서 주의해야할 사항은 다음과 같다. 현재 위치한 톱니바퀴는 무조건 회전한다.인접한 톱니바퀴는 극이 다를 경우만 반대방향으로 회전한다.이 과정을 재귀함수로 구현했다.아래 소스코드를 보면 이해하기가 쉽다.처음에 소스코드를 짤 때는 Solution 함수에 들어갔을 때 현재 톱니바퀴의 정보를 curr_arr이라는 전역변수에 Copy 해주고 현재 톱니바퀴는 회전시킨 후에 인접한 ..
문제https://www.acmicpc.net/problem/14890풀이너무너무 오래 걸린 문제다. 구현 능력을 보는 문제 같은데 예외처리 해야될 게 너무 많아 힘들었다.행과 열 각각 재귀함수로 검사하는 함수를 만들었다.함수에는 이전 칸의 높이와 동일한 칸의 수를 넘겼다.이전 칸과 현재 간 사이의 관계는 세 가지로 정의할 수 있다. 이전 칸보다 현재 칸이 높은 경우이전 칸보다 현재 칸이 낮은 경우이전 칸과 현재 칸의 높이가 같은 경우 이전 칸과 현재 칸의 차를 구해서 관계를 구했으며 차가 2이상인 경우는 길로 만들 수 없기 때문에 바로 함수를 종료시켰다.현재 칸이 높은 경우고 차가 1인 경우는 경사로를 만들어야 되는데 이 때 현재까지 쌓인 cnt값을 이용해서 이전에 존재하는 동일한 칸 수가 L 이상인 ..