AtCoder Beginner Contest 087_C - Candies
体調が悪くなったり、怪我をしたりで何かと手を付けられなかったけど
やっとこの問題が解けた!
当初は渡された入力データを元に
木構造を作って、一番高い合計値を出力すればいいのか!とか
思った。
最終的にどうやってポインタをつければいいんだ?みたいになって
配列でやればいいのかと気付き、最後の赤文字の部分だけでなんとかなることに気づく。
頭が悪いなりに何も答え見ずに解けたのは嬉しいな。
木構造で解こうとした残骸も載せておく。
#include <iostream>
#include <math.h>
using namespace std;
struct tree_node
{
int value;
struct tree_node *left;
struct tree_node *right;
};
tree_node *tree_root=NULL;
tree_node* create_new_node(int num)
{
tree_node *tree_new;
/* 新しいnodeを作成して,初期化する */
tree_new=(tree_node*)malloc(sizeof(tree_node));
if(tree_new==NULL)
exit(EXIT_FAILURE);
tree_new->left=NULL;
tree_new->right=NULL;
tree_new->value=num;
return tree_new;
}
void insert_tree1(int num,tree_node *node)
{
/* 1つも挿入されていない場合 */
if(node==NULL)
{
tree_root=create_new_node(num);
return;
}
//右側に付けていく。
if(node->right != NULL)
{
insert_tree1(num,node->right);
} else
{
/* 右側に追加する */
node->right=create_new_node(num);
}
return;
}
void insert_tree2(int num,tree_node *node)
{
//左側に付けていく。
if(node->left != NULL)
{
insert_tree2(num,node->right);
} else
{
/* 左側に追加する */
node->left=create_new_node(num);
}
return;
}
void print_value(tree_node *node)
{
if (node == NULL)
return;
print_value(node->left);
cout << node->value << "\n";
print_value(node->right);
}
void free_tree(tree_node *node)
{
if(node==NULL)
return;
/* まず子nodeのメモリを解放する */
free_tree(node->left);
free_tree(node->right);
/* 自分自身を解放 */
free(node);
}
int main (){
//合計値を算出するあれ。
int total = 0;
int total_value = 0;
//配列の列の長さをインプット
int side;
cin >> side;
//配列1行目の入力を定義する
int array1[side];
for (int i = 1; i <= side; i++){
cin >> array1[i];
insert_tree1(array1[i], tree_root);
}
//配列2行目の入力を定義する
int array2[side];
for (int j = 1; j <= side; j++){
cin >> array2[j];
insert_tree2(array2[j], tree_root);
}
for(int k = 1; k <= side ; k++){
for(int m = 1; m <= side; m++){
if(m <= k){
total = total + array1[m];
}
if(m >= k){
total = total + array2[m];
}
}
cout << k << "回目に分岐するルートの合計値は" << total << "\n";
if(total_value < total){
total_value = total;
}
total = 0;
}
cout << total_value << "\n";
return 0;
}