#문제 2096번: 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net #접근방법 이 문제는 접근방법은 쉬우나, 메모리 제한이 4MB밖에 안된다. 따라서 메모리 초과가 걸리지 않도록 배열의 수를 줄이는 방법을 생각해야한다. #풀이 #메모리 초과가 걸리는 풀이 #include #define max(x,y) (x > y ? x : y) #define min(x,y) (x < y ? x : y) int arr[100005][3]; int max_arr[100..
#문제 17070번: 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net #접근방법 이 문제는 방향성을 고려하여 파이프를 옮길 수 있는지 여부를 파악해서 dfs로 탐색을 해주면 된다. #풀이 #include int arr[20][20]; int n; void dfs(int x, int y, int direction){ arr[x][y]++; if(direction==0 || direction==2){ if(y
#문제 15686번: 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net #접근방법 이 문제는 모든 경우의 수를 구하는 브루트포스 유형의 문제이다. 브루트포스 알고리즘은 모든 경우의 수를 구하는 알고리즘이다. 비슷한 알고리즘인 백트래킹이 있는데 백트래킹 알고리즘은 모든 경우의 수를 찾을 때, 필요없는 부분은 가지치기하면서 구하는 알고리즘이다. #풀이 #include int house[105][2],hnum; int ..
#문제 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #접근방법 이 문제는 지도의 크기가 최대 8*8 = 64칸이 최대이므로 모든 경우의 수를 구해도 64*63*62*dfs가 걸리는 시간이므로 시간안에 돌아간다. 벽 3개를 설치하는 모든 경우의 수에서 dfs를 돌려서 안전영역이 최대가 되는 경우를 계산해주면 된다. #풀이 #include int arr[10][10]; int arr2[10][10]; int virus[64][2]; i..
#문제13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #접근방법이 문제는 숨바꼭질 2에서 변형된 문제이다. https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-12851%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-2-CC [백준] 12851번 : 숨바꼭질 2 [C/C++]#문제 12851번: 숨바꼭질 2 h..
#문제 13172번: Σ https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net #접근방법 이 문제를 처음 봤을 때 글이 너무 많고, 또 이해하기가 힘들었다. 두 세번정도 읽으니 전체적인 맥락과 수식들이 눈에 보여서 이해가 되었다. 페르마 소정리와 모듈러 역원에 대해 자세하게 적은 글이다. 다른건 다 필요없고 b^(x-2) ≡ b^-1 (mod X) 이 수식에서 b^(x-2) 이것을 구하는 것이 핵심이다. #풀이 #include #include using namespace std; using ll = l..
위에 사진을 보면 알겠지만 46일 동안 하루도 빠짐없이 문제를 풀었지만... 끊겨버렸다... 12월 27일에 휴가를 나가서 27일, 28일은 까먹지 않고 문제를 풀었지만, 문제의 29일!!! 이 때 디스코드로 친구들과 새벽까지 게임을 하고 침대에 눕는 순간!! 아뿔싸... 문제를 풀지 않았다는 사실과 나 자신과의 약속을 깨버렸다는 것에 대해 한심함과 속상함을 느꼈다. 이렇게 된 이상 휴가까지 나왔는데 마음껏 놀고 다시 군대에 들어가서 열심히 풀자고 자기합리화를 하고 휴가기간동안 문제를 풀지않고 실컷 놀았다. 오늘 생활관에 와서 문제를 풀었고, 다시한번 더 끊긴것에 대해 반성을 하며 오늘 부터 새로운 마음으로 시작하겠다! https://solved.ac/ solved.ac 우리 모두가 만들어가는알고리즘 문..
#문제 12865번: 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net #접근방법 모든 경우의 수를 따져야 하는 문제이다. 하지만 단순하게 백트래킹으로 접근하면 시간초과가 걸린다. 준서가 버틸 수 있는 무게가 100,000으로 제한이 되어있는 것에 초점을 두고 동적계획법으로 접근하면 된다. #풀이 #include #include using namespace std; i..
#문제 12851번: 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net #접근방법 너비 우선 탐색(bfs) 알고리즘을 사용하면 풀 수 있다. #풀이 #include #include using namespace std; int visit[100005]; int main(){ int n,k; int ans1 = 987654321; intans2 = 0; queue q; scanf("%d %d",&n,..
