목록c++ (497)

1일1알

백준 1099번 알 수 없는 문장 C++

1. 문장을 순회하면서 각각의 단어마다 현재 인덱스 - 단어의 크기 + 1 부터 현재 인덱스까지의 구성된 문자가 단어와 같은지 확인한다. ex) 현재 인덱스가 2이고, 단어가 "one" 이라고 하면 2 - 3 + 1 = 0 부터 2 까지 구성된 문자는 n, e, o 이고 이는 "one"과 구성된 문자가 같다. 2. 1에서 구한 인덱스 - 단어의 크기 + 1 이 0보다 작거나 구성된 문자가 같지 않다면 다음 문자를 검색한다. 1에서 구성된 문자가 같다면 순서를 바꾸는 비용을 구하고 dp로 해결할 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #incl..
알고리즘 2022. 2. 16. 13:52
백준 2296번 건물짓기 C++

1. 건물들을 x좌표 오름차순으로 정렬한다. 2. 좌표가 대각선 위로 올라가는 건물들과 대각선 아래로 내려가는 건물들의 이익을 따로 구하고 이익이 최대가 되는 경우를 구한다. 순열 문제와 비슷하게 푼 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; struct Building { int x; int y; int c; }; bool compare(const Building& lhs, const Building& rhs) { return lhs.x..
알고리즘 2022. 2. 15. 11:38
백준 2418번 단어 격자 C++

1. 3차원 dp 배열을 만든다. dp[ 행 ] [ 열 ] [ 문자열 크기 ] 2. 문자열의 0번 원소와 같은 행과 열의 dp [ 행 ][ 열 ][0] 을 1로 설정한다. 3. k를 1부터 문자열 크기 - 1 까지순회하면서 k번째 원소와 같고 주변에 k-1번째 원소가 있다면 dp[i][j][k]에 dp[주변 행][주변 열][k - 1]을 더해준다. 4. 모든 dp[행][열][문자열 크기 - 1]을 더한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; ..
알고리즘 2022. 2. 14. 11:15
백준 2705번 팰린드롬 파티션 C++

1. 자기 자신도 팰린드롬 파티션이기때문에 dp배열을 1로 초기화한다. 2. 0 ~ i - 1 까지 i 에서 뺀 값이 짝수이면 2로 나눠서 양쪽으로 배치해서 팰린드롬 파티션으로 만들 수 있기 때문에 dp[(i - 뺀 값) / 2] 를 dp[i]에 더해준다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector ..
알고리즘 2022. 2. 13. 12:08
백준 3258번 컴포트 C++

k를 1부터 증가시켜가면서 검사하면 되는데, 같은 구간을 계속 반복하는 경우도 있어서 반복되는것을 체크해주는것이 필요하다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int n, z, m; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> z >> m; vector circle(n + 1, 0); circle[z] = 1; for (int ..
알고리즘 2022. 2. 12. 12:04
백준 2082번 시계 C++

0부터 비교하면서 켜지지 않아야 할 곳에 불이 켜져있으면 넘어가고 모두 꺼져있다면 그 번호로 만들 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; vector nums(10, vector(15, true)); vector v(4, vector(15, true)); void Init() { nums[0][4] = false; nums[0][7] = false; nums[0][10] = false; nums[1][0] = false; nums[1]..
알고리즘 2022. 2. 11. 14:53
이전 Prev 1 ··· 67 68 69 70 71 72 73 ··· 83 Next 다음