알고리즘
1일 1알고리즘 실천
공통 프로젝트
이번주가 공통 프로젝트 마지막 주였고, 최종 발표까지 마무리되었다.
프로젝트 기간동안 아쉬웠던 팀도 있었지만 다들 너무 열심히 해준만큼 결과물도 잘 나와서 좋았다.
후기
벌써 하나의 프로젝트가 끝났다.
다음주부터는 특화 프로젝트 학습을 해야한다.
나는 특화 프로젝트를 안했기 때문에 벌써부터 학습해야할 것들이 많아 학습에 집중해야할 것 같다.
write
- 2월 3주차 결산 2022.02.20
- 2월 2주차 결산 2022.02.14
- boj 21939 문제 추천 시스템 Version 1 2022.02.11
- 2월 1주차 결산 2022.02.06
- boj 14238 출근 기록 2022.02.04
- boj 3673 나눌 수 있는 부분 수열 2022.01.31
- 1월 4주차 결산 2022.01.30
- 1월 3주차 결산 2022.01.23
- 1월 2주차 결산 2022.01.16
- 1월 1주차 결산 2022.01.09
- 12월 5주차 결산 2022.01.02
- boj 20500 Ezreal 여눈부터 가네 ㅈㅈ 2022.01.01
2월 3주차 결산
2022. 2. 20. 22:22
2월 2주차 결산
2022. 2. 14. 00:07
알고리즘
1일 1알고리즘 실천
공통 프로젝트
사실상 오늘이 개발 마지막 주다.
교육생분들이 새벽늦게나 주말에도 개발 하시는거 보니까 예전에 열심히 하던 때가 생각나도 그랬다.
다들 열심히 하는 모습이 보기 좋았고, 다음주에 발표인데 다들 잘하셨으면 좋겠다..!
후기
다음주에 최종 발표가 있는 날이다. 하지만 개발을 마무리하는 팀도 있을 것이고, UCC나 산출물을 제작하는 팀도 있을 것이다.
그러고보니 벌써 한 프로젝트가 끝나가고, 코치 생활도 벌써 1/3이 지나갔다.
시간 너무 빠른거 아닙니까??
다음주에는 부족했던 배포를 해보려고 한다. 물론 주변의 코치분들 도움 받으면서 해야할 일이다.
원래라면 더 일찍 했어야 했는데 계속 생각만 하다가 미뤄졌던 것 같다. 빨리 배워서 마스터해야겠다.
boj 21939 문제 추천 시스템 Version 1
2022. 2. 11. 13:12
https://www.acmicpc.net/problem/21939
21939번: 문제 추천 시스템 Version 1
tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령
www.acmicpc.net
recommend x
x가 1인 경우 리스트에서 가장 어려운 문제의 번호를 출력, 가장 어려운 문제가 여러 개면 문제 번호가 큰 것을 출력
x가 -1인 경우 리스트에서 가장 쉬운 문제의 번호를 출력, 가장 어려운 문제가 여러 개면 문제 번호가 작은 것을 출력
add P L
리스트에 난이도가 L인 문제 번호 P를 추가한다.
현재 리스트에 없는 문제만 들어오며, 이미 해결하여 리스트에서 제외된 문제가 다시 들어올 수 있다.
solved P
리스트에서 문제 번호 P를 제거한다. (해결한 것으로 간주)
문제들은 [문제 번호, 난이도] 로 정리되어 있으며, 들어온 순서대로 명령을 처리하는 문제입니다.
recommend 명령어에서 난이도가 가장 어려운 문제와 가장 쉬운 문제를 빠르게 뽑아내야 하므로 우선 순위 큐를 2개 사용하며, 최대 우선순위 큐와 최소 우선순위 큐를 같이 관리합니다.
각 문제의 난이도를 나타내기 위해 levellist라는 배열을 사용하였으며, 값이 0이 아니라면 리스트에 있는 문제라는 뜻입니다.
이를 이용하여 solved 시 levellist의 값을 0으로 바꾸고, recommend 명령어가 들어왔을 때 출력하기 전에 현재 최대/최소 우선순위 큐에 이미 solved된 문제가 있는지 확인하는 작업을 거친 후에 출력하도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <string>
#define MAX 100001
using namespace std;
typedef pair<int, int> pi;
priority_queue<pi, vector<pi>, less<pi> > mxq;
priority_queue<pi, vector<pi>, greater<pi> > mnq;
int levellist[MAX];
int N, M;
void func() {
string type;
int x, y;
cin >> M;
while (M--) {
cin >> type;
if (type == "add") {
cin >> x >> y;
mxq.push({ y,x });
mnq.push({ y,x });
levellist[x] = y;
}
else {
cin >> x;
if (type == "recommend") {
if (x == 1) {
while (1) {
int p = mxq.top().second;
int l = mxq.top().first;
if (levellist[p] == l) break;
mxq.pop();
}
cout << mxq.top().second << '\n';
}
else {
while (1) {
int p = mnq.top().second;
int l = mnq.top().first;
if (levellist[p] == l) break;
mnq.pop();
}
cout << mnq.top().second << '\n';
}
}
else {
levellist[x] = 0;
}
}
}
}
void input() {
int P, L;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> P >> L;
mxq.push({ L,P });
mnq.push({ L,P });
levellist[P] = L;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 15926 현욱은 괄호왕이야!! (1) | 2023.07.24 |
|---|---|
| boj 17299 오등큰수 (0) | 2021.02.22 |
| boj 9372 상근이의 여행 (0) | 2021.02.09 |
| boj 1158 요세푸스 문제 (0) | 2021.02.09 |
| boj 1918 후위 표기식 (0) | 2021.02.05 |
2월 1주차 결산
2022. 2. 6. 20:17
알고리즘
1일 1알고리즘 실천, 곧 200일
공통 프로젝트
설 연휴라 2일간 진행하였다.
하지만 연휴기간 동안 열심히 개발한 팀도 있어서 놀라웠다.
그만큼 프로젝트에 진심으로 하시는 것 같았고, 결과물이 기대된다.
팀 분위기가 걱정되는 팀도 있었지만 잘 해결될 것으로 보인다.
CS 스터디
이번주는 스케줄링을 맡았다.
그래도 어느정도 알고있던 부분이 있었기에 준비하는데 어려움이 있진 않았지만
슬슬 코치일 + 스터디가 합쳐지니 점점 준비하기 빡세질 것 같다.
스터디원이 질문하는거에 막힘도 있었어서 더 잘 준비해야겠다는 생각이 들었다.
후기
누적 조회수가 만 명이 넘었다. 와아~~
그냥 눌렀더니 딱 1만이길래 신기해서 찍었다 ㅎㅎ
이제 공통 프로젝트도 2주밖에 남지 않았고, 다음 프로젝트를 위한 준비와 개인 CS 역량 향상을 위한 학습이 필요하다고 느낀다.
CS는 언제해도 부족하다는 생각이라 공부하면서 매일 늦게 퇴근하는게 잘한 일이 되기위해 노력중이다.
다음주는 데일리 컨텐츠로 GitLab 관련하여 교육생분들께 몇가지를 알려드릴 생각이고,
배포 관련해서도 다른 코치의 도움을 받으며 시도해볼 생각이다.
그래도 얻어가는게 많아서 좋다는 생각이 든다 :)
+ 알고리즘 블로그면서 알고리즘은 안올리고 회고만 쓰고있는데.. 1주에 한 문제 정도는 올려야겠다는 생각이 든다 ㅠ
boj 14238 출근 기록
2022. 2. 4. 09:08
https://www.acmicpc.net/problem/14238
14238번: 출근 기록
스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의
www.acmicpc.net
dp[a][b][c][pre1][pre2]: 현재까지 A, B, C가 각각 a, b, c번 출근하였고, 전날 출근을 pre1, 전전날 출근을 pre2가 했을 때 올바른 출근 기록인지 여부
1일마다 A, B, C 중 한 명이 무조건 출근하며
A: 매일 출근할 수 있다.
B: 출근한 다음날은 반드시 쉬어야 한다.
C: 출근한 다음날과 다다음날은 반드시 쉬어야 한다.
위 조건들을 이용해서 구현 해야 합니다.
리턴 받은 값이 1이면 올바른 출근기록이므로 순서대로 출력해주시면 됩니다.
0을 리턴받았으면 올바른 출근기록이 없으니 -1을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 51
using namespace std;
string str;
int dp[MAX][MAX][MAX][3][3];
int cnt[3];
int N;
int dfs(int a, int b, int c, int pre1, int pre2) {
if (a + b + c == N) return 1;
int &ret = dp[a][b][c][pre1][pre2];
if (ret != -1) return ret;
ret = 0;
if (a < cnt[0]) {
ret = dfs(a + 1, b, c, 0, pre1);
if (ret == 1) {
cout << 'A';
return ret;
}
}
if (b < cnt[1]) {
if (pre1 != 1) {
ret = dfs(a, b + 1, c, 1, pre1);
if (ret == 1) {
cout << 'B';
return ret;
}
}
}
if (c < cnt[2]) {
if (pre1 != 2 && pre2 != 2) {
ret = dfs(a, b, c + 1, 2, pre1);
if (ret == 1) {
cout << 'C';
return ret;
}
}
}
return ret;
}
void func() {
memset(dp, -1, sizeof(dp));
if (!dfs(0, 0, 0, 0, 0)) cout << "-1\n";
}
void init() {
N = str.size();
for (int i = 0; i < N; i++) {
cnt[str[i] - 'A']++;
}
}
void input() {
cin >> str;
init();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 12978 스크루지 민호 2 (0) | 2022.06.08 |
|---|---|
| boj 10986 나머지 합 (0) | 2022.03.08 |
| boj 3673 나눌 수 있는 부분 수열 (0) | 2022.01.31 |
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |
| boj 1135 뉴스 전하기 (0) | 2021.11.15 |
boj 3673 나눌 수 있는 부분 수열
2022. 1. 31. 12:36
https://www.acmicpc.net/problem/3673
3673번: 나눌 수 있는 부분 수열
양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오. 예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누
www.acmicpc.net
M으로 나누어 떨어지는 연속하는 부분 수열의 합의 갯수를 찾는 문제입니다.
이 문제의 키워드는 "연속" 이며, 누적 합을 이용합니다.
|
1
2
|
M = 4, N = 8
2 1 2 1 1 2 1 2
|
cs |
위의 입력을 예시로 우선 수열의 누적합을 구해 각각의 MOD M을 구합니다.
|
1
2
|
sum = 2 3 5 6 7 9 10 12
MOD M = 2 3 1 2 3 1 2 0
|
cs |
그러면 위와 같이 누적 합과 누적 합의 MOD M 값을 카운팅합니다.
M = 4이므로
나머지가 0인 갯수는 1
나머지가 1인 갯수는 2
나머지가 2인 갯수는 3
나머지가 3인 갯수는 2
이렇게 됩니다.
여기서 나머지가 1인 부분 수열을 설명하면
sum(1 ~ 3), sum(1 ~ 6)의 나머지가 1로 같다는 말입니다.
그러면 sum(4 ~ 6)의 나머지는 0이라는 말이 됩니다.
따라서 나머지가 같은 부분 수열에서 2개를 뽑는 조합을 구하면 되는 겁니다.
나머지가 1인 부분 수열은 2개이므로 2개 중에 2개를 뽑는 경우의 수: 1
나머지가 2인 부분 수열은
sum(1 ~ 1), sum(1 ~ 4), sum(1 ~ 7)로 3개로
3개 중에 2개를 뽑는 경우의 수로 3이라는 답이 나옵니다.
같은 방식으로 나머지가 0 ~ M - 1일 때의 경우의 수를 모두 구해줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <iostream>
#include <cstring>
#define MAX_N 50001
#define MAX_M 1000000
using namespace std;
typedef long long ll;
ll dp[MAX_N], cnt[MAX_M];
int N, M;
void func() {
ll ans = cnt[0];
for (int i = 0; i < M; i++) {
if (cnt[i] < 2) continue;
ans += ((cnt[i] * (cnt[i] - 1)) / 2LL);
}
cout << ans << '\n';
}
void input() {
cin >> M >> N;
for (int i = 1; i <= N; i++) {
cin >> dp[i];
dp[i] += dp[i - 1];
cnt[dp[i] % M]++;
}
}
void init() {
memset(cnt, 0, sizeof(cnt));
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
init();
}
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 10986 나머지 합 (0) | 2022.03.08 |
|---|---|
| boj 14238 출근 기록 (0) | 2022.02.04 |
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |
| boj 1135 뉴스 전하기 (0) | 2021.11.15 |
| boj 17090 미로 탈출하기 (0) | 2021.06.27 |
1월 4주차 결산
2022. 1. 30. 22:08
알고리즘
1일 1알고리즘 실천
공통 프로젝트 진행
이번주에 기획 발표를 진행했다.
일단 모든 팀들의 발표를 들었을 때의 소감은.. 그냥 놀라웠다.
프로토 타입을 시연하는 UCC를 제작한 팀도 있었고, 저작권 문제 확인을 위해 법률 상담까지 받은 팀도 있었다.
팀당 적어도 1명씩은 능력자가 있는건지 진행 속도도 우리 기수에 비해 엄청 빠르다는 느낌을 받았다.
빨리 결과물을 보고싶다는 생각이 들었다.
토비 스프링 스터디
1챕터 공부한 것을 복습하는 개념으로 진행하였다.
하지만 내가 모르고 있던 개념들이 많았고, 스터디원들이 설명해 주는 것을 거의 듣기만 한 것 같다.
다음 스터디에는 부족한 점들 보완해서 내가 설명할 수 있도록 준비해야겠다는 생각이 들었다.
후기
오랜만에 부산에 내려와서 친구들을 만났다.
학교에서 대학 어디갈건지 대화했었던 애들인데 취업 얘기를 하고있더라..
벌써 다들 취업하는 시기구나 다시 느끼게되었다.
대화를 하면서 내 생각을 다시 바로잡을 수 있는 좋은 시간이 되었고, 더 열심히 살아야겠다는 생각이 들었다.
1월 3주차 결산
2022. 1. 23. 22:24
알고리즘
1일 1알고리즘 실천
공통 프로젝트 진행
프로젝트 2주차였고, 나름 업무가 익숙해지려고 한다.
데일리 컨텐츠를 준비하면서 Git, Jira에 대해 더 알아갈 수 있어서 좋았다.
기술적인 문제는 내가 보안해야 할 문제고, 답변 잘 할 수 있도록 해야겠다.
CS 스터디
이번주부터 운영체제 학습을 시작했다.
나는 프로세스와 스레드 부분을 맡아서 진행했고, 생각보다 어려웠고, 스스로도 준비가 미흡했다는 생각이 들었다.
다음부터는 핵심내용 위주로 준비 잘해야겠다는 생각이 들었다.
토비 스프링 스터디
토비 스프링 1챕터를 학습하였고, 스터디를 진행하였다.
생각보다 내가 아는부분이 없었고, 기본적인 개념부터 다시 해야겠다는 생각이 들었다.
그래도 사람들과 함께 정보 공유할 수 있다는게 좋았다.
후기
Jira 사용을 독려했더니 전반적으로 Jira 사용을 많이 하시는것 같아 기분이 좋았다.
다음엔 Git 관련 컨텐츠를 준비해야겠다.
교육생 때보다 코치 때가 시간이 더 빠른 것 같다.
업무 + 공부를 병행하다보니 더 그렇게 느끼는건진 모르겠다.
그래도 이런 시기를 겪어야 성장한다는 생각에 저질렀으니 해야지 그래
1월 2주차 결산
2022. 1. 16. 22:26
알고리즘
1일 1알고리즘 실천
CS 스터디
이번주는 저번주에 못했던 LCA 알고리즘 파트를 진행했고, 팀원들은 해시 테이블, 세그먼트 트리 부분을 진행했다.
이제 알고리즘은 끝났고, 다음 주부터 운영체제를 진행한다.
이번에도 준비 잘해서 안까먹도록 해야겠다는 생각이 든다.
공통 프로젝트 진행
코치로서의 프로젝트가 시작되었다.
우리반의 모든 팀과의 미팅을 가졌고, 생각보다 진행속도, 퀄리티 부분에서 대단하다는 생각이 들었다.
나중에 결과물이 기대가 된다.
스프링 학습 및 정리
원래 이번주에 진행 되었어야 할 스터디가 준비 미흡으로 인해 1주 미뤄졌다.
그래서 더 열심히 공부를 했지만 오랜만에 하는 스프링이라 그런지 생각보다 많이 어려웠다.
내일 스터디 진행 하면서 보완해야할 점을 찾아야겠다.
후기
벌써 프로젝트 1주차가 지났다.
팀 미팅을 가져보니 교육생 때 생각이 많이 났었다.
교육생 때 진행했었던 프로젝트를 예시로 설명도 해주는 내 모습을 보니 뭔가 기분이 이상했다.
내 능력 선에서는 최선을 다해 코칭해야겠다는 생각이 들고,
1주에 2개의 스터디를 하는 만큼 내 부족한 부분도 보완하면서 더 열심히 살아야겠다는 생각이 들었다.
'잡담' 카테고리의 다른 글
| 1월 4주차 결산 (0) | 2022.01.30 |
|---|---|
| 1월 3주차 결산 (0) | 2022.01.23 |
| 1월 1주차 결산 (0) | 2022.01.09 |
| 12월 5주차 결산 (0) | 2022.01.02 |
| 12월 4주차 결산 (0) | 2021.12.26 |
1월 1주차 결산
2022. 1. 9. 20:08
알고리즘
1일 1알고리즘 실천
프로젝트 명세서 학습
맡은 트랙에서 사용하는 기술들을 학습했고, 발표를 진행했다.
내가 맡은 트랙에 인원이 2명밖에 되지 않아서 시간이 많이 부족했던것 같다.
준비를 하면서도, 발표가 끝나고도 더 많은 부분을 학습하지 못해서 아쉬움이 남았던것 같다.
다음주에는 질문이 쏟아질 예정인데 다른 트랙들도 열심히 학습해야겠다는 생각이 든다.
후기
이번주는 스터디를 진행하지 못했다.
면접이 있는 팀원도 있고 해서.. 집중을 하는게 맞겠다 싶었다.
그리고 어제 백신을 맞았는데.. 이번에도 부작용이 씨게 온듯 하다. 부작용 없는사람 부럽네요..
다음주부터는 코치로서 교육생분들도 만나고 할텐데 실수없이 잘 해야겠다는 생각이 든다.
'잡담' 카테고리의 다른 글
| 1월 3주차 결산 (0) | 2022.01.23 |
|---|---|
| 1월 2주차 결산 (0) | 2022.01.16 |
| 12월 5주차 결산 (0) | 2022.01.02 |
| 12월 4주차 결산 (0) | 2021.12.26 |
| SSAFY 5기 회고 (0) | 2021.12.25 |
12월 5주차 결산
2022. 1. 2. 20:19
알고리즘
1일 1알고리즘 실천
CS 스터디
이번주는 dp와 비트마스크를 정리하였다.
dp는 가장 좋아하는 알고리즘이라 순조롭게 마친것 같다.
다음주는 LCA인데 다시 복습하는 마음으로 임해야겠다.
SSAFY 코치 교육
저번주 결산에는 떨어졌다고 했지만 추합해버렸다.. ㅎㅎ
코치가 어떤 일을 하는지, 중요한게 뭔지 하나씩 교육받고있다.
준비 잘해서 최대한 실수 안해야겠다는 생각이 들었다.
후기
2021년이 벌써 끝나고 2022년이다. 흑..
코치 떨어지고 앞으로의 취준생활에 대해 걱정하고 있었는데 추합이 돼서 너무 다행이라고 생각한다.
다음주 CS 스터디는 알고리즘 마지막 부분이다.
그 다음부터는 컴구, OS, DB, 네트워크와 같은 어려운 과목이 배정되어 있으므로 코치와 병행하는게 힘들수도 있겠다는 생각이 든다.
하지만 지금이 내 인생에서 정말 중요한 기간이고, 힘든 일을 겪고나면 그만큼 내가 얻는게 많지않을까 하는 생각으로 열심히 해야겠다.
'잡담' 카테고리의 다른 글
| 1월 2주차 결산 (0) | 2022.01.16 |
|---|---|
| 1월 1주차 결산 (0) | 2022.01.09 |
| 12월 4주차 결산 (0) | 2021.12.26 |
| SSAFY 5기 회고 (0) | 2021.12.25 |
| 12월 3주차 결산 (0) | 2021.12.19 |
boj 20500 Ezreal 여눈부터 가네 ㅈㅈ
2022. 1. 1. 16:59
https://www.acmicpc.net/problem/20500
20500번: Ezreal 여눈부터 가네 ㅈㅈ
문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.
www.acmicpc.net
1과 5로만 이루어진 N자리 양의 정수 중에서 15의 배수가 몇 개인지 구하는 문제입니다.
15의 배수는 3의 배수 * 5의 배수입니다.
따라서 3의 배수이고, 5의 배수인 것을 찾으면 됩니다.
dp[N][R]: N자리의 양의 정수를 3으로 나눈 나머지가 R인 경우의 수
따라서 먼저 5의 배수를 만들어 놓고, 3으로 나눈 나머지를 확인하도록 합니다.
우선 N = 1일때는 15의 배수가 없으므로 패스합니다.
N = 2일때는 5의 배수가 15, 55가 있습니다.
15는 3으로 나눈 나머지가 0이므로 dp[2][0]에 해당하고,
55는 3으로 나눈 나머지가 1이므로 dp[2][1]에 해당합니다.
따라서 초기 값은 dp[2][0] = 1, dp[2][1] = 1입니다.
그 다음 N = 3일때는 N = 2일 경우에 1 또는 5를 붙인 경우를 더해주시면 됩니다.
dp[3][0]은 dp[2][1]에서 앞자리에 5를 더한 경우 + dp[2][2]에서 앞자리에 1을 더한 경우
dp[3][1]은 dp[2][0]에서 앞자리에 1을 더한 경우 + dp[2][2]에서 앞자리에 5를 더한 경우
dp[3][2]는 dp[2][0]에서 앞자리에 5를 더한 경우 + dp[2][1]에서 앞자리에 1을 더한 경우
따라서 점화식은 위와같이
dp[i][0] = dp[i - 1][1] + dp[i - 1][2]
dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
dp[i][2] = dp[i - 1][0] + dp[i - 1][1]
이렇게 됩니다.
결과로는 MOD를 한 값을 출력해야 하므로 더하면서 MOD값을 넣어주도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#define MAX 1516
#define MOD 1000000007
using namespace std;
int dp[MAX][3];
int N;
void init() {
dp[2][0] = 1;
dp[2][1] = 1;
for (int i = 3; i < MAX; i++) {
dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
}
}
void input() {
cin >> N;
cout << dp[N][0] << '\n';
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
input();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 14238 출근 기록 (0) | 2022.02.04 |
|---|---|
| boj 3673 나눌 수 있는 부분 수열 (0) | 2022.01.31 |
| boj 1135 뉴스 전하기 (0) | 2021.11.15 |
| boj 17090 미로 탈출하기 (0) | 2021.06.27 |
| boj 1648 격자판 채우기 (0) | 2021.06.22 |