블로그 언저리인 무언가

문제 : 4388 받아올림 4388번: 받아올림 어린이에게 여러자리 숫자의 덧셈을 가르칠 때는 오른쪽 자리부터 왼쪽으로 하나씩 계산하는 방법을 가르쳐준다. 이때, 받아올림이 발생하게 되며 아이들은 여기서 혼란에 빠진다. 받아올림이� www.acmicpc.net 두 수를 입력받아 덧셈을 할 때, 받아올림이 일어나는 횟수를 출력하는 문제이다. 두 수의 끝자리부터 순서대로 더하면서 받아올림이 생기는 경우를 체크해주면 된다. Code #include #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); while (1){ ll a, b, ans=0; cin >> a >> b; if (a==0 && b==..

문제 : 9370 미확인 도착지 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 예술가들의 출발지와 목적지 후보가 주어졌을때, 어떤 도로를 지나서 최단거리로 갈수있는 모든 후보를 출력하는 문제이다. Dijkstra 알고리즘을 사용해 출발지~도착지까지의 최단거리가 출발지~교차로+도로의 길이+교차로~도착지의 최단거리와같은 경우를 찾아 출력하면 된다. Code #include #define ll long long #define INF 1e9+7 using namespace std; struct ABC{ ll ..

문제 : 1753 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 방향 그래프가 주어졌을 때, 시작점에서 다른 모든 점까지의 최단경로를 구해 출력하는 문제이다. Dijkstra 알고리즘을 사용해 순회한 후 경로가 존재하는지 체크해 배열의 값을 출력하면 된다. Code #include #define ll long long #define INF 987654321 using namespace std; typedef pair pll; struct ABC { ll idx, dst; ..

문제 : 17953 디저트 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나� www.acmicpc.net 각 날마다 디저트가 주는 만족감이 주어질 때, 최대로 얻을 수 있는 만족감을 출력하는 문제이다. 날짜를 N, 디저트의 종류를 M이라 할 때 그냥 모든 경우의 수를 구하면 O(M^N)이므로 당연히 시간 초과가 난다. DP 배열을 만들어 전날까지의 만족감 중 최대를 골라 계속 갱신해주면 O(N*M^2)로 시간제한 안에 해결할 수 있다. Code #include #define ll long long using namespace std; ll N, M..

문제 : 15724 주지수 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 �� www.acmicpc.net 직사각형의 범위가 주어질 때 그 안에 사는 사람 수의 합을 출력하는 문제이다. 배열의 길이가 N, 주어지는 범위의 개수가 M일 때 그냥 구하게 되면 O(N^2*M)으로 시간 초과이므로 누적합 배열을 이용해 시간을 O(N^2+M)으로 줄여서 구하면 된다. Code #include #define ll long long using namespace std; ll N, M, T, arr[1050][1050]; int main(){ ios::sy..

문제 : 1342 행운의 문자열 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작� www.acmicpc.net 어떤 문자열이 주어졌을 때 문자를 재배치해 인접한 문자가 같지 않은 문자열의 경우의 수를 구하는 문제이다. 문자열을 정렬한 후 next_permutation을 이용해 모든 경우의 수를 확인하면 된다. Code #include #define ll long long using namespace std; string S; ll ans; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> S;..

문제 : 14499 주사위 굴리기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 지도의 크기와 각 칸에 쓰여있는 정수가 주어졌을 때, 주사위를 굴리는 명령이 주어질 때 위에서 보이는 면을 출력하는 문제이다. 각 방향으로 이동할 때 각 주사위의 면이 어떻게 회전하는지 알려주는 roll배열을 선언한 후 해당하는 순서로 값의 순서를 바꾸고 해당하는 칸의 명령을 수행하면 된다. Code #include #define ll long long using ..