민우의 코딩노트

[문제] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [풀이] 다이나믹 프로그래밍(DP), Prefix Sum [코드] #include using namespace std; int n,m; int a[100004], d[100004]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; d[0] = 0; for(int i=1; i> a[i]; d[i] =..

[문제] https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net [풀이] 다이나믹 프로그래밍(DP) [코드] #include using namespace std; int d[10005]; int mod = 10007; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; d[1] = 1; d[2] = 2; for(int i=3; i

[문제] https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [풀이] 다이나믹 프로그래밍(DP) [코드] #include using namespace std; int d[1005][3]; int r[1005], g[1005], b[1005]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1; i> r[i] >> g[i] >> b[i];..

[문제] https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net [풀이] 정렬 [코드] #include using namespace std; int n; long long a[100005]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i> a[i]; sort(a, a+n); int cnt = 0; long long mxval= -(111

[문제] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [풀이] 다이나믹 프로그래밍 [코드] #include using namespace std; int d[20]; int main() { ios::sync_with_stdio(0); cin.tie(0); d[1] = 1; d[2] = 2; d[3] = 4; for(int i=4; i> t; while(t--){ int n; cin >> n; cout

[문제] https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [풀이] 다이나믹 프로그래밍 [코드] #include using namespace std; int s[305]; int n; int d[305][3]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=1; i> s[i]; if(n==1){ cout

[문제] [풀이] 정렬 [코드] #include using namespace std; int n,m; int a[1000005], b[1000005], c[10000005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=0; i> a[i]; for(int i=0; i> b[i]; int aidx=0, bidx = 0; for(int i=0; i

[문제] [풀이] 머지 소트(merge sort)를 이용한 정렬 풀이 [코드] #include using namespace std; int n=10; int arr[1000001]; int tmp[1000001]; void merge(int st, int en){ int mid = (st+en)/2; int lidx = st; int ridx = mid; for(int i=st; i n; for(int i=0; i> arr[i]; merge_sort(0, n); for(int i=0; i

[문제] https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [풀이] C++ next permutation 이용(조합), 시뮬레이션 [코드] #include using namespace std; #define X first #define Y second int board[55][55]; int n,m; vector chicken; vector house; int main(void) { ios::sync_with_stdio(0)..

[문제] https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net [풀이] 시뮬레이션 + 90,180,270,360도 회전 알고리즘 [코드] #include using namespace std; int board1[21][21]; int board2[21][21]; int n; void rotate(){ int tmp[21][21]; for(int i=0; i