알고리즘 부수기

문제링크 : https://www.acmicpc.net/problem/11060 칸 수(1>n; for(int i=0;i

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODE 상원이의 같은 반 친구 수 (2T; for(int test_case=1;test_case>N>>M; for(int i=0;i

문제링크 : https://www.acmicpc.net/problem/10164 N(세로 사이즈, 우선 경로의 수는 int 범위 안에서 수행 가능하지만 "15 * 15밖에 안되네 그냥 int로 하자"라고 생각하면 안된다. 나중에 해보면 알겠지만 입력으로 "15 15 0"이 들어올 경우가 최다 경로인데 40,116,600개가 나온다. 18 * 18이상은 int 범위가 넘어가게 된다. [ 사이즈만 보고 방심하면 히든 케이스에서 터져버린다. 다른 문제 풀 때도 주의해야할 점 ] 이제 풀이로 들어가보면 아이디어 자체는 간단하다. 중학교 때 수학에서 배운 방법을 사용하는 것이다. 이 맵에서 1번부터 8번을 거쳐 15번까지 가는 최단경로의 수는 (1번부터 8번까지 가는 최단경로의 수) * (8번부터 1..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWdXrXraFloDFAWn&categoryId=AWdXrXraFloDFAWn&categoryType=CODE A ( 원하는 이동 횟수 ) [ 1 문제가 이해가 안돼서 테스트케이스를 보고 분석을 했다. )( 는 1번만에 ()라는 올바른 문자열을 만들 수 있다. )())((는 4번만에 ()()()라는 올바른 문자열을 만들 수 있다. 문제 설명에서 문자열 T가 올바른 문자열이면 ( T ) 도 올바른 문자열이다. 라고 되어있지만 1) )))(((을 ()()()로 만드는 데는 3+2+1 = 6 번이 필요하다. 2) )))(((을 ((()))로..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWgqsAlKr9sDFAW0 정수 N (1 D5라서 겁먹고 시작했는데 단순한 문제였다. 문제가 어렵다기 보다는 테스트 케이스가 10,000개에 수의 범위가 10^12기 때문에 어떤 방법으로 시간을 줄여서 풀 것인지가 중요한 문제이다. 따로 줄이는 과정을 생각해보지도 않았고 while문 돌렸는데 풀려서.. 다른 사람들이 어떤 방법으로 시도를 했고 시간초과로 고민을 하는지는 잘 모르겠다. -------------------------------------------------------------------------------------..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE 없음 100만 이하의 모든 소수 출력하기 "에라토노스의 체"라는 이론을 사용할 것이다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 간단하게 설명하면 우선 100만 이하의 2의 배수를 모두 지운다. 다음으로 3의 배수를 모두 지운다. 진행 중 지워..

문제링크 : https://www.acmicpc.net/problem/14720 우유 가게 수 n n개의 가게 정보 ( 0 : 딸기우유, 1 : 초코우유, 2 : 바나나우유 ) 최대로 마실 수 있는 우유의 개수 역시 단순한 dp 문제이다. 0(딸기우유)번 가게일 경우 이전의 2(바나나우유)번 가게의 값 중 Max +1을 하고 1(초코우유)번 가게는 이전의 0(딸기우유)번 가게의 값 중 Max +1, 2(바나나우유)번 가게는 이전의 1(초코우유)번 가게의 값 중 Max +1을 하면 된다. 여기서 주의해야할 예외는 1. 맨 처음에는 딸기우유를 한 팩 마신다. 이다. 즉, 1과 2가 나오더라도 0이 나오기 전이라면 값을 갱신해서는 안된다. 예외처리를 해줘야 하는 경우는 2..

문제링크 : https://www.acmicpc.net/problem/11727 길이 n이 주어진다. 2 x n 크기의 직사각형을 채우는 방법의 수 (%10,007) 계단을 1칸 2칸씩 오를 때의 경우의 수와 같은 전형적인 dp문제이다. 따라서 (2 x (n-1))의 경우와 (2 x (n-2))의 경우를 더해주면 된다. 여기서 주의해야할 점은 (2 x (n-1))의 경우를 2번 더해줘야 한다는 점이다. (즉, x 2) 이유는 2 x n 크기의 직사각형을 채울 수 있는 방법을 시뮬레이션 해보면 알 수 있다. 위 사진에서 ?가 그려진 직사각형을 2 x n 크기로 보자. 그러면 아래 그림처럼 1칸 적은 직사각형에서 2 x 1을 더하는 경우와 2칸 적은 직사각형에서 2 x ..