맛있는감귤

문제 : https://www.acmicpc.net/problem/134582015년 삼성 SW 역량 테스트와 유사한 문제(?)시험 문제를 정확히 모르지만 비슷한 문제라며 돌고 있다.SW 역량테스트가 첫 시행됐을 때 문제라 그런가 쉬운편 문제 해결1. 총 감독관은 시험장마다 반드시 한 명 존재해야하기 때문에 총 감독관의 감시 범위를 빼준다.2. 응시자가 남으면 필요한 부감독관 수(a[i]/C)만큼 더해주고3. 찌꺼기가 남아있으면 +1 해주고 아니면 말고.123456789101112131415161718#include int main(){ long long a[1000002]; long long N,B,C,sum=0; scanf("%lld",&N); for(int i=0;i0) sum++; } printf..

문제 : 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/13913기존 1697 숨바꼭질 과 같은 문제지만 추가로 지나온 경로를 출력을 요구한다는 점에서 차이가 있다.처음에는 queue에 경로 벡터를 추가해서 노드마다 경로 값을 가지는 무식한 짓을 벌였다.어처피 목적지에 도달하는 최소 경로중 하나만 출력하면 되기 때문에 배열 하나로 지나온 경로를 관리하는 방법으로 AC를 얻었다.visited[다음 경로] = 현재 경로 가 된다. 그리고 목적이에 도달했을 때 목적지에서 출발지까지 뒤로 탐색해 vector에 push한 다음 다시 출력하게 되면 원하는 경로가 출력될 것이다.123456789101112131415161718192021222324252627282930313233343536373839404..

문제 : 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]..