맛있는감귤

문제 : https://www.acmicpc.net/problem/15264와 7로 만 이루어진 숫자를 구하면 된다.이런 DP문제도 있는데 경우의 수가 아닌 N이하의 가장 큰 수만 구하면 되기 때문에 완전탐색으로 해결 가능1의 자리수 4, 7에서 부터 하나씩 4와 7을 붙여 나가도록 하자.1 : 4, 72 : 44, 47, 74, 77 3 ....이런 식으로 .123456789101112131415161718192021222324252627282930include #include using namespace std;int main(){ int N,ans=0; queue q; scanf("%d",&N); if(4

문제 : https://www.acmicpc.net/problem/1953BFS를 이런식으로도 활용할 수 있구나 했던 문제한명만 싫어하는 경우는 없기 때문에 A가 B를 싫어한다면 둘이 서로 다른 팀에만 배정하면 된다.블루 화이트 상관없이 아무데나 넣어버리자.flag를 순서대로 이용하여 섞이지 않도록 함.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include using namespace std; int N;bool visited[102];vector v[102];queue q;priority_queu..

문제 : https://www.acmicpc.net/problem/3197출처Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #2 - Seniors 2번 2573 빙산, 3055 탈출 문제의 하드버전문제 해결 순서1. 백조의 만남 가능 여부2. 해빙. 테두리만 녹이기3. 만날 때까지 반복해결 방법은 3055 탈출문제와 유사하지만 R, C 값이 1500이기 때문에 백조 만남 가능 여부 탐색시 TLE가 발생할 수도 있다. (이거 때문에 개고생) 문제 해결 방안제일 처음 백조 이동 후 만날 수 없다면 방문 한 곳은 다시 방문할 필요없다.만날 수 있냐 없냐만 확인하면 가능하기 때문에 백조의 위치를 변경..

문제 : https://www.acmicpc.net/problem/5567출처Olympiad > 일본정보올림피아드 예선 > JOI 2010 예선 3번 상근이 - 친구(1) - 친구의 친구(2) 상근이로부터 깊이가 2인 노드까지만 탐색한다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std;int N,M,ans=0,cnt=0;vector v[502];bool visited[502];queue q; int main(){ scanf("%d%d",&N,&M); while(M--){ int a,b; scanf("%d%d",&a,&b); v[a].push_back(b..

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