맛있는감귤

문제 : https://www.acmicpc.net/problem/31902016년 삼성 하반기 공채 SW 역량테스트 오전 문제째로탈출과 같이 나온 오전 문제. 한 때 인기몰이를 했던 2048 게임의 축소판이다.이 문제는 최대 이동횟수가 5이기에 DFS나 BFS 두 가지 방법으로 모두 해결가능하다.하지만 한 쪽으로 기울일 때 숫자가 합쳐지는 과정을 어떻게 구현하느냐가 문제!상하좌우를 각각 짜서 코드 가독성이 매우 안좋음나는 한 쪽으로 치우쳐지면서 숫자가 합쳐지는 것을 vector로 짰다. 0(빈공간)을 제외한 숫자를 벡터에 받고 v[k]와 v[k+1]을 비교한 후 같으면 v[k]*2, v[k+1]=0으로 만들어주고 다시 숫자판에 초기화해주었음.포스팅하기 민망한 코드이지만 필요할 수도 있는 사람을 위해서 ..

문제 : https://www.acmicpc.net/problem/134592016년 삼성 하반기 공채 SW 역량테스트 오전 문제더러운 BFS 문제이다. 백준에 오후 기출문제는 정확히 구현되어있지 않지만 오전 문제는 거의 비슷하게 구현되어있다.개인적으로 오전문제가 오후문제보다 어려웠던 것 같다. 판을 돌려 두개의 구슬을 움직여 10번안에 빨간 구슬을 꺼낼 수 있는가가 문제의 핵심이다.판을 돌린다고 했지만 구슬만 상하좌우로 옮기면 된다. 문제 핵심1. 빨간 구슬과 파란 구슬의 visited배열을 하나로 관리2. 빨간 구슬과 파란 구슬 서로의 위치는 상관없이 상하좌우 이동 후 방향에 따라 구슬의 위치관계 고려해주고 조정한다.3. 파란 구슬이 빠져 나오는 경우는 무시 (빨간 구슬이 먼저나와도 파란 구슬이 같이..

문제 : https://www.acmicpc.net/problem/1261일반적인 미로찾기에서 아주 사알짝 업그레이드 된 문제.1. 벽 어느 벽을 부쉈냐에 따라 이동경로가 달라질 수 있기 때문에 주의하도록 하자.2. 또 최소 이동거리가 아닌 부순 벽의 개수가 최소가 되어야 하기 때문에 모든 이동경로를 비교해야 한다. 비슷한 문제2206 벽 부수고 이동하기 / 해설14442 벽 부수고 이동하기 2 / 해설 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include using namespace std; struct Pos{ public: int r,c,crash; Pos(){} Pos(int..

문제 : https://www.acmicpc.net/problem/1074기초 분할 정복 문제재귀를 구현할 머리가 안되는지 완전 탐색이나 DP보다 이게 더 어렵게 느껴질 때가 많다.다행히 2^N꼴이기 때문에 쉽게 접근이 가능하다.n==2, 2*2의 제일 작은 사각형이 될 때까지 4등분으로 나누어주고 (line. 31~34) Z모양으로 cnt를 차례대로 증가시켜주자.123456789101112131415161718192021222324252627282930313233343536373839#include #include int N,R,C,cnt=0;void dnc(int n,int r,int c){ if(n==2){ if(r==R && c==C) { printf("%d\n",cnt++); return ; }..

문제 : https://www.acmicpc.net/problem/5214출처Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 4번 이 문제는 입력만 잘 받으면 BFS로 해도 시간초과가 나지 않는다.핵심은 임의의 열의 개수를 어떻게 vector에 push하느냐 이다.문제 테스트 케이스를 돌려보면1 : 10 11 2 : 10 3 : 10 12 4 : 11 5 : 11 13 6 : 12 13 14 7 : 12 13 8 : 14 9 : 14 10 : 1 2 3 11 : 1 4 5 12 : 3 6 7 13 : 5 6 7 14 : 6 8 9 가 나온다. 잘 활용해서 풀어보도록 하자. 12345678910111213141..

문제 : https://www.acmicpc.net/problem/14226간단한 BFS이지만 visited 배열을 잘 활용하지 못한다면 원하는 정답이 안나올 것이다.현재 글자수 뿐만아니라 클립보드에 저장 돼 있는 글자 수도 고려해줘야 한다.핵심 visited[글자수][클립보드]1234567891011121314151617181920212223242526272829303132333435363738394041#include #include using namespace std;int S,cnt=0;queue q;bool visited[2002][2002];int main(){ scanf("%d",&S); q.push(make_pair(1, 0)); visited[1][0]=1; while(!q.empty()..

문제 : https://www.acmicpc.net/problem/14442 벽 부수고 이동하기의 업그레이드 문제입니다.기존의 문제는 벽 부술 수 있는 기회가 한번뿐이지만 이 문제는 K번이라는 것 빼고는 같은 문제에요.visited배열을 3차원으로 만들어 visited[r][c][0 or 1 벽 부수기 스킬 사용 여부]를visited[r][c][k]로 관리해주면 그만입니다.입력이 뭉쳐서 나오니 잘 해결합시다. 저는 char 배열로 이어서 받았습니다.int형 배열로 받고 싶다면 반복 for문으로 scanf("%1d",&map[i][j]); 이런 식으로 받으면 되겠죠.그리고 이동이 1부터 시작하는 것도 유의하신다면 쉽게 AC받으실 수 있을거에요~코드의 이해 안되시는 부분은 댓글 남겨주시면 정성껏 답변 해드리..

문제 : https://www.acmicpc.net/problem/9095출처ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001 PC번 DP로 해결할 수 있는 문제입니다.1부터 4까지만 보면dp[1] = 1dp[2] = 1+1, 2dp[3] = 1+2, 1+1+1, 2+1, 3dp[4] = 1+3, 1+1+2, 2+2, 1+1+1+1, 1+2+1, 2+1+1, 3+1 이렇게 된다. 자세히보면 i번째 값은 i-1, i-2, i-3번째를 합한 값과 같다.12345678910111213#include int main(){ int T; scanf("%d",&T); while(T--){ int N, n[12]; n[0]=0, n[1]=1, n[2]..

문제 : https://www.acmicpc.net/problem/11657최단거리를 찾는 문제같은데 타임머신이 있거나 시간을 역행하는 문제, 음수 가중치가 존재하는 대다수의 문제는 벨만-포드 알고리즘으로 해결가능합니다.다익스트라 알고리즘 같은 경우 해당 노드에 존재하는 간선을 보고 가중치가 가장 작은 값을 선택하게 됩니다.그렇기 때문에A -> B -> C / A -> C 의 루트에서1 5 -4 1 3의 값을 가질 때 노드 A의 간선의 가중치 5와 3만을 비교하기 때문에 원하는 답을 도출할 수 없습니다.왜냐하면 1 -> 5 -> -4이 더 최단 거리가 되기 때문이죠.그렇기 때문에 간선을 비교하고 또 노드의 개수-1만큼 또 비교를 해주면 됩니다. (도착지 노드까지 가는 간선은 전체 노드개수를 넘지 않기 때..

문제 : https://www.acmicpc.net/problem/9517출처Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #2 1번 원형 식탁에서 210초를 넘겼을 때 폭탄을 가지고 있는 사람을 출력하면 됩니다.이렇게 원형인 구조가 있을 때는 %로 관리해주면 편하게 할 수 있습니다.저는 시작이 0이 아닌 1부터 시작이기 때문에 헷갈려서 처음 입력받을 때 -1 해주고 출력할 때 다시 +1 해주었습니다. #include int main(){ int pos, N, total_time = 210; scanf("%d %d",&pos, &N); --pos; for(int i=0;i