'KOI' 태그의 글 목록

[백준] 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 ..

Problem Solve/Brute Force 2020. 3. 27. 14:13

[백준] 1018번 체스판 다시 칠하기 (C)

문제 주소 백준 1018번 체스판 다시 칠하기 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 알고리즘 브루트 포스 힌트 정답 배열을 만들어 놓고 비교한다. 풀이 B와 W가 반복해서 나와야 하는데 B가 먼저 올 수 도 있고 W가 먼저올 수도 있다. 이것을 따로 계산해주면 복잡해서 W가 먼저 나온다고 가정을 하고 문제를 푼다. 이 때 색을 칠하는 개수와 64 - 색을 칠하는 개수중 더 작은 수가 색을 칠하는 최소 개수가 된다. 64 - 색을 칠하는 개수가 B가 먼저 나올 경우를 생각해 주는 것이다. #i..

Problem Solve/Brute Force 2020. 3. 27. 01:21

[백준] 7568번 덩치 (C)

출처 한국정보올림피아드 지역본선 2013 초등부 2번 문제 주소 백준 7568번 덩치 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 www.acmicpc.net 풀이 0 ~ n-1을 확인하면서 덩치가 큰 사람의 수를 세어준다. #include using namespace std; i..

Problem Solve/Brute Force 2020. 3. 22. 22:33

[백준] 2231번 분해합 (C)

출처 ICPC Asia Regional Seoul 2005 B번 문제 주소 백준 2231번 분해합 힌트 모든 경우를 다 확인해도 제한 시간 안에 가능하다. 풀이 제한시간이 2초이고 입력받는 n의 범위가 1,000,000이하이다. 이는 O(n)풀이가 가능하다는 말이다. 따라서 1부터 n까지 확인하여 분해합이 n과 같다면 그 수를 출력하면 된다. #include using namespace std; int main(){ int n; cin>>n; for(int i=1;i=1;j/=10){ sum+=tmp/j; tmp%=j; } if(sum==n){ cout

Problem Solve/Brute Force 2020. 3. 22. 22:10

[백준] 1260번 DFS와 BFS (C++)

문제 주소 백준 1260번 DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 DFS, BFS 풀이 간단한 DFS와 BFS 구현 문제이다. DFS는 재귀함수와 스택으로 구현할 수 있고, BFS는 q로 구현해야 한다. DFS를 하고 check배열을 초기화 해주어 BFS를 한다. #include #include using namespace std; int graph[1001][1001]; int check[1001]; int n, m; void dfs(i..

Problem Solve/DFS & BFS 2020. 3. 21. 15:37

[백준] 2206번 벽 부수고 이동하기 (C++)

문제 주소 백준 2206번 벽 부수고 이동하기 알고리즘 BFS 힌트 어떤 위치에 온 상태가 벽을 부수고 온 것인지, 벽을 부수지 않고 온 것인지 구분 해야 한다. 풀이 위치(a, b)와 상태(w : 벽을 부쉈다면 1 부수지 않았다면 0)를 원소로 가지는 dot구조체를 만들어 준다. check배열도 위치와 상태를 담을 수 있도록 3차원으로 선언 해 준다. 현재의 위치가 목표 위치라면 ans를 출력하고 main 함수를 종료 해 준다.q를 다 확인 할 때까지 목표점에 도착하지 못하였다면 목표점에 도달할 수 없는 것이므로 -1을 출력해준다. 벽이 있고 벽을 뚫지 않았다면 q에 넣어주고 벽이 없다면 check배열을 하여 중복되지 않도록 q에 넣어준다. #include #include using namespace ..

Problem Solve/DFS & BFS 2020. 3. 21. 15:09

[백준] 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[다음위..

Problem Solve/DFS & BFS 2020. 3. 21. 01:01

[백준] 1023번 유기농 배추 (C)

문제 주소 백준 1012번: 유기농 배추 알고리즘 DFS, Flood Fill 힌트 Flood Fill 알고리즘을 사용하여 구역의 개수를 구한다. 풀이 배추들의 위치를 입력받기 전에 in배열과 check배열을 초기화 해주어야 한다. check가 되어 있지 않으면서 배추가 있는 곳을 탐색하여 주변 배추들이 있는 곳을 check한다. #include using namespace std; int n,m; int in[50][50]; int check[50][50]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; void fill(int a, int b){ check[a][b]=1; for(int i=0;i=n || nb>=m||nax; for(int q=0;q>m>>n>>c; f..

Problem Solve/DFS & BFS 2020. 3. 20. 23:50

[백준] 2485번 키 순서 (C)

출처 한국정보올림피아드 지역본선 2011 초등부 4번 문제 번호 백준 2458번 키 순서 코드업 4714 : 키 순서 알고리즘 DFS 힌트 나보다 큰 아이보다 작은 아이와의 관계는 알 수 없음 나보다 큰 아이보다 큰 아이는 나보다 큼 나보다 작은 아이보다 작은 아이는 나보다 작음 나보다 작은 아이보다 큰 아이와의 관계는 알 수 없음 풀이 들어오는 입력들을 그래프에 저장해 줄 때 1과 2로 구분하여 저장해줌으로써 누가 더 큰 아이인지 구분이 가능하게 해준다. 나보다 큰 아이들과 나보다 작은 아이들의 합이 전체 아이의 수 - 1 (n-1) 이라면 모든 나의 등 수를 알고있다고 할 수 있다. 따라서 dfs함수를 구현 할 때 몇 번째 아이에 대해 탐색할건지 n와 어느 방향에 대해(큰 아이들, 작은 아이들) 탐색..

Problem Solve/DFS & BFS 2020. 3. 20. 01:07

[백준] 7596번 토마토 (C)

출처 한국정보올림피아드 지역본선 2013 초등부 3번 문제 번호 백준 7569 토마토 코드업 :4773 토마토 (초등) 알고리즘 3차원 BFS 힌트 배열에 토마토가 익는 날짜를 저장 문제 풀이 이 문제 풀이의 핵심은 배열에 토마토가 익는 날짜를 저장한다는 것이다. 익은 토마토의 입력이 1로 들어오기 때문에 day배열에 저장될 숫자는 그 위치의 토마토가 익는 날 +1이 된다. 토마토의 위치를 나타낼 dot 구조체를 만들어주고 dot을 넣을 큐q를 만들어 준다. 3차원이기 때문에 방향 배열의 크기는 6*3이 된다. BFS이기 때문에 가장 먼저 갱신된 값이 날짜의 최소값이다. 따라서 check배열을 만들어 주지 않고 day배열을 check배열처럼 사용할 수 있다. BFS가 끝나고 day배열에 들어있는 최대값을..

Problem Solve/DFS & BFS 2020. 3. 16. 18:17

낭만 IT

KOI → (15)건