::SemiColon;;

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이번문제는 dp(다이나믹 프로그래밍)를 이용하여 푸는 문제이다. 예시들을 쭉 세워보면 n = 1은 0, n = 2는 1, n = 3은 1, n = 4는 2, n = 5는 3, n = 6은 2 이다. 위의 예시들 중 n = 6을 보면 6은 3으로도 나누어 떨어지고, 2로도 나누어 떨어진다. 따라서 6을 3으로 나눈값, 2로 나눈값, 1을 뺸값을 다 비교해보아야한다. 즉 dp[6] = min(dp[6/3], dp[6/2], dp[6-1])이다. 이를 토대로 점화식을 세워보면 dp[i] = min(dp[i/3] (i..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이 문제의 푸는 방법을 먼저 말하자면 피보나치 배열과 똑같은 답이다. 이유는 n = 1일때 아래와 그림과 같이 2×1 하나로 되어 결과는 1이다. n = 2일때는 아래와 그림과 같이 2×1 2개, 1×2 2개로 조합하여 만들 수 있기에 결과는 2이다. n = 3일때는 두가지 경우로 나눌 수 있는데 왼쪽의 그림은 n = 2의 그림에 단지 2×1 1개만 붙인 것이다. 왼쪽의 그림은 n = 1의 그림에 단지 1×2 2개만 ..

https://www.acmicpc.net/problem/1003 피보나치 함수는 대표적인 다이나믹프로그래밍 문제이다. 피보나치 함수는 f(0) = 0, f(1) = 1, n>=2, f(n) = f(n-1) + f(n-2)의 꼴이다. 위의 문제는 0이 나오는 횟수와 1이 나오는 횟수를 출력하는 것이다. 따라서 n=0: {1,0} n=1: {0,1} n=2: {1,1} n=3: {1,2} n=4: {2,3} .... 이렇게 이어진다. 위의 순서를 보고 규칙을 찾으면 n=i: {i-1 의 첫번째 원소 + i-2 의 첫번째 원소, i-1 의 두번째 원소 + i-2 의 두번째 원소}이다. 따라서 이에 맞게 함수를 작성하면 pair fibo(int a) { if (dp[a] != make_pair(0, 0)) r..

https://www.acmicpc.net/problem/1149 기본적인 DP문제입니다. 문제를 푸는 아이디어는 집을 색칠할 수 있는 3가지 색깔의 경우의수를 모두다 구해보는 것입니다. 코드로는 for (int i = 1; i < N; i++) { dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][0]; dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + input[i][1]; dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + input[i][2]; } 이렇게 될것입니다. dp[i][j]는 i번째 집을 j색깔로 칠했을때의 최소비용입니다. 따라서 dp[i][0]은 i번째 집을 0번 페인트로 칠했을때 ..

https://www.acmicpc.net/problem/10815 기본적인 이분탐색 문제입니다. 소스코드 #include #include using namespace std; int N, M, arrn[500000], a; void Input() { cin >> N; for (int i = 0; i > arrn[i]; cin >> M; sort(arrn, arrn + N); } bool BS(int target) { int l = 0, r = N - 1, m; while (l > a; if (BS(a)) cout

https://www.acmicpc.net/problem/21609 BFS를 곁들인 구현문제였다... 저는 문제를 잘 못읽어서 다 풀어놓고도 몇분 헤맸던 문제였어요 이 문제는 문제에 써있는 순서대로 블럭그룹을 찾고, 블럭그룹을 지우고, 중력을 작용하고, 90도 반시계회전하고, 중력을 작용하는것을 함수를 짜서 순서대로 돌아가도록 하면 되는 문제였다. 주의할점으로는 첫번째, 기준블럭을 정하는 규칙과 블럭그룹을 정하는 규칙을 정확히 이해해야한다. 처음에 이것을 잘못 이해해서 몇분 헤맸습니다..ㅠㅠ 두번째, 무지개색깔 블럭을 검은블럭을 뺀 나머지 색깔블럭들도 접근할 수 있도록 해야한다. 저는 무지개색깔을 어떤 색깔이 접근을 했다면 다시 초기화하여 다른 색깔도 접근을 할 수 있도록 작성했습니다 소스코드 #incl..

이 문제는 구현문제로 어떻게 구현할지 생각하는데 조금 생각해봐야하는 문제이다. 특별하게 생각해야할 점은 아래의 두점이다. 토네이도가 이동하는 경로 토네이도는 1칸가고 방향바꾸고, 1칸가고 방향바꾸고, 2칸가고 방향바꾸고, 2칸가고 방향바꾸고, 3칸가고 방향바꾸고.... 이러한 규칙을 통해 토네이도의 가는 경로를 쉽게 구현해 낼 수 있었다. 토네이도의 방향에따라 달라지는 모래가 날리는 좌표 토네이도가 상하좌우 방향에 따라 모래가 날리는 좌표가 조금씩 달라지는데 한번 모든 방향 4가지의 좌표를 계산해봐서 연관성을 찾아본다면 방향이 180도 다른 것의 좌표는 x축 또는 y축 대칭이라는 것을 알 수 있다. 방향이 90도 다른 것들의 좌표는 y=x(45도의 직선) 대칭이라는 것을 알 수 있다. 따라서 하나의 방향..

일반적인 구현 문제이다 #include #include #include using namespace std; typedef struct fireBall { int m, s, d; } FB; int N, M, K; vector map[51][51], tmp[51][51]; int dx[8] = { -1,-1,0,1,1,1,0,-1 }, dy[8] = { 0,1,1,1,0,-1,-1,-1 }; void Input() { cin >> N >> M >> K; for (int i = 0; i > r >> c >> m >> s >> d; map[r][c].push_back({ m, s, d }); } } void mapCopy(vector m1[][5..

택시가 태울 다음 손님을 BFS로 찾은 후 다음 손님까지 태우러 가는 거리 + 손님의 도착지 까지의 거리를 연료에서 뺀 후 또 다음 손님을 구하는 이 방식을 반복하면 되었다. 주의할 점은 연료가 0일때 손님이 있는지 찾아 보는 것이랑 택시에서 손님까지, 손님의 출발지부터 손님의 목적지까지 갈 수 있는지도 체크를 하여야했다. #include #include #include #include #define pii pair using namespace std; struct client { int clix, cliy, desx, desy; bool isArrived; } Client[400]; pii taxi; int map[21][21]; int N, M, fuel; int dx[4] = { 0,0,1,-1 }..

1. 상어들이 움직인다 2. 겹친 상어상태에서 지울 상어를 지운다. 3. 냄새시간을 하나씩 다 센다 4. 새로운 냄새를 다시 만든다. 주의할 점은 딱히 머 없는거 같다. #include #include #define pii pair using namespace std; struct s { int x, y, d; bool alive; } shark[401]; int N, M, k, prior[401][5][4], rS, T; pii map[20][20]; //smell map int dx[5] = { 0,-1,1,0,0 }, dy[5] = { 0,0,0,-1,1 }; void Input() { cin >> N >> M >> k; rS = M, T = 0; int a; for (int i = 0; i < N..