[백준] 1436번 영화감독 숌 (C)

문제 주소 백준 1436번 영화감독 숌 알고리즘 브루트 포스 힌트 7번째 짜리에서 6이 연속으로 3번 이상 나오는 경우가 10000번이 넘는다. (9*9*9*9*5) 문제 풀이 n의 범위가 10000 이하이기 때문에 1부터 1씩 증가 시키면서 n번째의 수를 찾아도 제한 시간안에 풀 수 있다. count6 함수는 6이 연속된 개수를 확인하는 함수이다. #include using namespace std; int count6(int i){ int cnt=0,flag=0; while(i>1){ if(i%10==6){ if(!flag) flag=1; cnt++; } else if(flag){ if(cnt>=3) return cnt; flag=0; cnt=0; } i/=10; } return cnt; } int ..

• format_list_bulleted Brute Force
• · 2020. 3. 27.
• textsms

[백준] 1697번 숨바꼭질 (C++)

출처 USACO US Open 2007 Contest Silver 2번 문제 주소 백준 1697번 숨바꼭질 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 알고리즘 BFS 힌트 check 배열(방문 배열)에 그곳에 가게 되는 시간 + 1을 저장한다. 풀이 수빈이가 이동할 수 있는 위치는 3군데가 있다. 각 각의 위치가 주어진 범위를 벗어나지 않는 지 확인을 한 후 왔던 곳인지 확인을 한다. 처음 위치를 1로 하고 (이는 check배열의 본질을 잃지 않기 위함이다.) check[다음위..

• format_list_bulleted DFS & BFS
• · 2020. 3. 21.
• textsms

[코드업] 3500 : 지뢰 찾기 2 (C)

알고리즘 : DFS, Flood Fill 풀이 단순한 탐색 알고리즘 문제지만 다른 문제들과 다른점은 4방향이 아닌 8방향을 탐색해야 한다는 것이다. 방향배열을 8*2로 잡아주고 탐색을 해주면 된다. 문제를 풀기에 앞서 이해를 해보면 다음과 같다. 특정 칸의 숫자는 그 칸 주위의 8개의 칸 중에 지뢰의 개수를 나타낸다. 클릭한 칸에서 시작하여 (1)의 숫자가 0이 아닐때 까지 탐색한다. (이때 탐색도 8방향이다) 탐 탐색한 칸은 (1)의 숫자, 탐색하지 않은 칸은 _로 출력한다. 내가 선택한 칸이 지뢰일 경우 그 칸을 -1 나머지는 _를 출력한다. in배열은 입력 데이터 이고 map배열은 지뢰의 갯수를 세어 놓는 배열이다. ( 탐색이 끝나는 지점이 될 것이다. ) 처음에 in 배열을 모두 돌아 map 배열..

• format_list_bulleted DFS & BFS
• · 2020. 3. 13.
• textsms

[코드업] 2605 : 캔디팡 (C)

알고리즘 Flood Fill 풀이 문제 그대로 같은 색으로 이어진 칸들의 갯수를 세면 된다. 배열 범위를 벗어나는지 좀 더 편리하게 체크하기위해서 배열의 크기를 9*9로 잡아 주었다. 입력값에 0이 없기 때문에 in[i][j]가 0이라면 배열의 범위를 벗어난 것으로 확인할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142#includeusing namespace std; int in[9][9];int check[8][8]; // 한번 방문했던 곳 체크 int dir[4][2]={{1,0}, {0,1}, {-1,0}, {0,-1}}; // 방향배열 int ans; int search(int a,int b){ /..

• format_list_bulleted DFS & BFS
• · 2020. 3. 9.
• textsms

[백준] 2457번 공주님의 정원 (C)

출처 2011 지역본선 초등2 문제 주소 백준 2457번 공주님의 정원 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1a>>b>>c>>d; in[i].start=a*100+b; in[i].end=c*100+d; } sort(in,in+n,cmp); int now=301,ans=0,index,max=0; for(int i=0;i1130) break; // 오늘(now)을 포함하는 꽃들 중 가장 오래 심을 수 있는 꽃을 찾는다. if(max

• format_list_bulleted Greedy
• · 2020. 3. 8.
• textsms

[백준] 8980번 택배 (C)

출처 2013 전국 본선 초등2 알고리즘 그리디 힌트 상자를 싣고 갈 구간을 보자. 문제 풀이 그리디 알고리즘으로 간단하게 풀리는 문제지만 뭐에 대해서 그리디를 적용시킬지 찾는게 쉽지 않다. 결론 부터 말하자면 상자가 트럭에 실려 있는 구간이 짧은 순으로 확인하면 된다. 구간이 같다면 먼저 실을 수 있는 상자를 선택한다. 따라서 상자를 목적지, 출발지 순으로 오름차순 정렬하면 된다. 그 뒤 반복문으로 앞에서 부터 살피면 되는데 이번에 선택된 상자(now)가 트럭에 실려있어야 할 구간을 살피고 모두 실을 수 있다면 now의 cost를, 용량이 초과된다면 남은 용량 만큼을 그 구간에 더해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

• format_list_bulleted Greedy
• · 2020. 3. 7.
• textsms