문제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 이상인 ..
문제https://www.acmicpc.net/problem/14889풀이시간을 너무 잡아먹은 문제였다. 초기 접근을 이상하게 해서 시간이 오래 걸린 점도 있었지만 재귀호출을 어려워하는 부분이 아직 있는 것 같다. dfs와 백트래킹을 통해서 모든 경우를 돌아보는 완전탐색 문제다.dfs로 스타트 팀으로 뽑을 선수 번호를 뽑는다스타트 팀으로 뽑은 선수가 N/2 명이 되면 두 팀의 능력치 차이를 구한다.위 과정을 반복한다.스타트 팀으로만 뽑는 이유는 어차피 뽑지 않은 선수는 링크 팀이기 때문이다. 소스코드에 주석을 보면 이해하기가 쉽다.소스코드#include #include #include using namespace std; #define MAX_SIZE 21 int n; bool is_used[MAX_SI..
문제https://www.acmicpc.net/problem/14503풀이한시간 반동안 비슷하게 푼 거 같았지만 결국은 테스트케이스도 못맞췄다.아직도 재귀호출을 구현하려면 머리가 아프다.dx[4], dy[4] 에 북(0), 동(1), 남(2), 서(3) 순으로 저장을 했다.현재 방향을 direction이라고 했을 때 북쪽을 보고 있는 경우를 제외하고 왼쪽 방향은 direction-1이기 때문에 이 점을 이용해 다음 방향을 정했다.다음 칸이 청소해야되는 칸일 경우에 그 칸으로 이동한 후에 나머지 방향의 탐색은 하지 않는다.다음 칸이 벽이거나 청소한 칸일 경우에는 방향만 바꿔주고 탐색을 계속 진행한다.네 방향 모두 검사를 마친 후는 모두 청소한 칸이거나 벽인 경우이기 때문에 방향을 유치한 채로 후진을 해줬다..
문제https://www.acmicpc.net/problem/14502풀이 재귀함수를 통해 벽 3개를 추가한다.벽이 3개가 쌓였을 때 BFS를 통해 바이러스를 퍼트리고 안전영역의 크기를 구한다.1로 돌아가 반복한다소스코드#include #include #include #include using namespace std; #define MAX_N 9 int n, m; int map[MAX_N][MAX_N]; int temp_map[MAX_N][MAX_N]; int ans; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; vector virus; vector safety_Zone; void CopyMap(int(*a)[MAX_N], int(*b)[MAX_N]) {..
문제https://www.acmicpc.net/problem/2003풀이과정1차원 배열에서 각각 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 기법인 투 포인터(two pointers) 문제다.left ~ right 구간의 합을 확인하면 된다.(93%,1초) 에서 “틀렸습니다”가 떴다. 왜 그런가 찾아봤더니 한 가지 예외처리를 해줘야되는 문제였다.만약 left+1 이 right보다 커질 경우에는 left와 right의 자리를 바꿔줘야된다.소스코드 #include using namespace std; #define MAX_N 10001 int n, m; int a[MAX_N]; int ans; void solution() { int left = 0, right = 0,now_Sum..
문제https://www.acmicpc.net/problem/1182풀이과정recursion을 통해 간단하게 해결할 수 있는 문제다. 입력 된 숫자들을 더하는 경우, 더하지 않고 그냥 넘어가는 경우 두 가지로 나누어서 재귀호출을 하면 된다.소스코드#include using namespace std; #define MAX_N 21 int n, sum; int num[MAX_N]; int ans; void sub(int i, int prev_Sum) { // index를 끝까지 했으면 종료 if (i == n) { // sum과 같으면 ans++ if (prev_Sum == sum) ans++; return; } // 숫자를 사용하는 경우 sub(i + 1, prev_Sum + num[i]); // 사용하지..
문제https://www.acmicpc.net/problem/1987풀이과정입력으로 알파벳 대문자로 이루어진 보드판이 주어진다. (0,0) 부터 문제에서 주어진 규칙에 따라 인접한 상하좌우로 이동할 수 있는 최대칸 수를 출력해야하는 문제다.DFS로 접근을 했고 처음에는 문제를 잘못보고 이전 알파벳하고 방문하는 알파벳만 다르면 방문할 수 있는 줄 알았다.문제를 자세히 보면 밟아온 보드판에서 사용된 알파벳은 다시 밟을 수 없다고 한다.그래서 알파벳의 사용여부를 체크하는 배열을 만들어 DFS를 돌렸다.소스코드#include #include #include using namespace std; #define MAX 21 int r, c; char alpha[MAX][MAX]; // 입력되는 보드판 bool ch..