재귀 문제 #include using namespace std;using ll = long long;int a, b, m;ll rec(ll a, ll b, ll m){ if(b == 1) return a % m; ll val = rec(a, b/2, m); val = val * val % m; if(b % 2 == 0) { return val; } else return val * a % m;}int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> a >> b >> m; cout
PS
dp문제인가 뭐지 했는데, BFS로 풀 수 있었다.시작지점을 0으로 놓고, ranged-based for을 이용해서 cur-1, cur+1, cur*2를 방문하여 숫자를 하나씩 올려주었다. #include #include #define X first#define Y secondusing namespace std;int dist[100002];int n, k;int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; fill(dist, dist + 100001, -1); dist[n] = 0; queue Q; Q.push(n); while(dist[k] == -1){ int cur ..
좀 까다로운 문제였는데, 언제든지 응용해서 나올 수 있을 것 같은 느낌을 받았다.탈출을 하기 위해서는 nx, ny가 0이나 n, m 크기를 넘어가야했다. 반복을 돌리다가 넘어간 경우 현재의 dist에서 1을 더해 출력해주었다. 또한 불의 dist와 J의 dist를 비교하여 불의 dist가 더 낮은 경우 이미 불이 빠르게 도착한 상태이므로, continue를 통해 다음 큐로 넘어갈 수 있도록 했다. #include #include #define X first#define Y secondusing namespace std;int n, m;string board[1002];int distF[1002][1002];int distJ[1002][1002];int dx[4] = {1, 0, -1, 0};int dy[..
bfs도 어느정도 적응이 되어가는 것 같다. 앞서 풀었던 미로 탐색 문제랑 비슷했는데, 토마토는 여러곳에서 bfs를 시작하게 될 수 있다는 것에 차이가 있었다.고민하다가 토마토가 있는 지점 모두를 큐에 먼저 넣어놓고 bfs를 시작했고, board가 0인지점을 dist -1로 초기화했다. 만약 dist가 -1이 남아있는 지점이 있으면 도달할 수 없는 곳이 있는 것으로 판단하고, -1을 출력해서 마무리했다. 이전에 봤던 max함수를 써먹었고, dist도 잘 써먹었다. #include #include #define X first#define Y secondusing namespace std;int n, m;int board[1005][1005];int dist[1005][1005];int dx[4] = {1,..
쉬운 bfs 문제. dist 배열을 만들어서 가는 길을 카운트해서 결과값을 얻을 수 있도록 했다. 4 6101111101010101011111011 input이 위와 같을 경우에는 int 배열 board를 2차원으로 만드는 것이 아니라 string 배열로 처리할 수 있었다. for(int i = 0; i > board[i]; } for(int i = 0; i 위와 같이 입력을 받아서 구현하는 방법을 알았고, 2차원 배열을 -1로 모두 채우기 위해서 for문을 사용하고 fill함수를 통해 짧게 구현할 수 있었다. #include #include #include #define X first#define Y secondusing namespace std;int dist[105][105];s..
mx = max(mx, area); 오랜만에 푸니까 자꾸 까먹는데 꼭 기억해두자!굉장히 쉬운 bfs 문제인듯하다.빠르게 짜다가 dx dy를 자꾸 dx dx로 쓰는데 조심해서 짜자! #include #include #define X first#define Y secondusing namespace std;int board[505][505];int vis[505][505];int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};int n, m;queue> Q;int main(){ cin >> n >> m; for(int i = 0; i > board[i][j]; } } int mx = 0; int num = 0; for(int..
문득 떠올릴 수 있는 풀이는 사실 O(N^2) 풀이인데, 배열을 잘 활용하니 O(N)에도 가능하다는 것을 알았다.func(int arr[], int N){ int occur[101] = {}; for(int i = 0; i
굉장히 낮은 난이도의 문제이다.배열을 전역변수로 선언하고 0으로 초기화했다.그리고 배열을 알파벳의 그릇이라고 생각하고, 배열의 처음부터 차례대로 a-z까지 라고 생각하고 사용했다.a를 입력받으면 arr[0]를 증가시키고 이런식이다. arr[c - 'a'] 에서 눈여겨 볼 것은 c-'a'가 어떠한 숫자로 바뀐다는 것인데, 문자 a는 10진수로 변환할시 97을 뜻하고, c는 반복을 돌면서 어떠한 문자를 값으로 받았을 것이다. 거기서 그 문자에 'a'를 빼주면 97 c가 받은 어느 알파벳의 숫자(아스킥코드)에서 빠져서 0~25의 배열에 차례대로 알파벳들의 순서를 정확히 매기고 숫자를 증가시킬 수 있었다.A는 65를 뜻하는 것도 기억 해야겠다. 그리고 char 0은 10진수 48이다. #include using..
