너와 나의 스토리

문제: https://www.acmicpc.net/problem/1248 문제 풀이: 각 값들을 행렬로 표현하면 다음과 같다. 대각선은 자기 자신을 나타낸다. 즉, arr[idx][idx]의 부호는 $n_{idx}$의 부호이다. $n_{1}$ $n_{2}$ $n_{3}$ $n_{4}$ $n_{1}$ n1 n1+n2 n1+n2+n3 n1+n2+n3+n4 $n_{2}$ n2 n2+n3 n2+n3+n4 $n_{3}$ n3 n3+n4 $n_{4}$ n4 - 해당 숫자의 부호가 음수이면, 가능한 값은 [-10,1] - 해당 숫자의 부호가 양수이면, 가능한 값은 [1,10] - 해당 숫자의 부호가 0이면, 가능한 값은 '0' 이렇게 범위를 좁혀 문제를 풀 수 있다. 모든 경우의 수를 구하는 것이 아니라, 적당한 값..

문제: https://www.acmicpc.net/problem/1987 문제 풀이: 그냥 간단한 DFS 문제이다.` TestCase: 2 4 CAAB ADEM => 6 소스 코드: 더보기 #include #include #include #include #include #include #include using namespace std; int n, m,res; char arr[22][22]; bool visit[22][22],exist[26]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; void func(int x, int y, int cnt=1) { for (int i = 0; i < 4; i++) { int curx = x + dx[i]; int c..

문제: https://www.acmicpc.net/problem/3109 문제 풀이:처음 열의 맨 윗 칸에서 시작 ㄴ> 위 칸이 최대한 위쪽으로 진행해야 (↗) 많이 설치 가능 - ↗ → ↘ 순으로 갈 수 있는 방향 확인하고 진행하므로 가장 많이 설치할 수 있게 이동 함- 즉, visit을 지우지 않고 기록하면서 진행하면 됨 소스 코드:https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-3109

문제: https://www.acmicpc.net/problem/1941 문제 풀이: * 처음에는 단순하게 dfs로 풀었는데 ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ 이런식으로 이동이 불가능 했다 -> fail - 무작위로 7명을 뽑아낸 후 - '이다솜파(S)'가 더 많은지 (4명 이상) 확인YES -> 모두 연결되어 있는가 (bfs 이용)YES -> cnt++; 소스 코드:https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-1941 Testcase:case1:YYYYYYYSYYYSYSYYYSYYYYYYY -> 답1: 48 case2:YYYYYYYSYYYSSSYYYSYYYYYYY -> 답1: 592 * 다른 방법: 훨씬 빠름bfs, dfs 둘 다..

문제: https://www.acmicpc.net/problem/2210 문제풀이1: 방문한 루트를 string( tmp)으로 기록하고 tmp.size()==6일때 map에 저장해 map에 존재하지 않을 경우만 cnt++ 해서 cnt를 출력하는 방법으로 문제를 풀었다. 소스코드: https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-2210 결과:메모리: 2652 KB 시간: 4ms 문제풀이2: 개선된 방법 map을 사용하지 않고 bool check[10][10][10][10][10][10]; 을 사용해 존재하는 경로를 파악하였다 소스코드: https://gist.github.com/hovy1994/8b11fc944de34cd39b..

문제:https://www.acmicpc.net/problem/1339 문제 풀이1: 백트래킹 이용 void func(int cur,int pos, int cur_sum,int sum,int visit) cur: 몇번째 단어를 보는 중인지 알려줌pos: 현재 보는 단어에서의 위치cur_sum: 현재 보는 단어에서 현재위치까지의 합sum: 지금까지의 합visit: 지금껏 사용한 숫자를 표시 모든 수를 대입해보고 가장 결과 값이 큰 값을 출력 소스 코드: https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-1339 결과:메모리: 1992KB 시간: 632ms 문제 풀이2: 각각의 위치에 따른 값을 부여ex) ABCC위치의 값은 1B위..

문제: https://www.acmicpc.net/problem/2023 문제 풀이:- '에라토스테네스의 체' 이용해서 풀려고 bool arr[100000000] 만들면 메모리 초과가 난다 ㅎㅎ - 맨 첫 숫자는 2 3 5 7만 가능하다 - 홀수만 가능하다ㄴ> 시간 많이 줄어들기 때문에 그때그때 소수인지 판단해줘도 됨. 소수코드:https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-2023